╨╧рб▒с>■ 68■ 5 ье┴Y ┐,bjbjєWєW 4С=С=, ]ВВВВВВВЦЦЦЦЦв<ЦъЄЄЄЄЄЄЄЄЄп▒▒▒▒▒▒$▄Ї╨Ї╒ВЄЄЄЄЄ╒(ВВЄЄЄ(((Є6ВЄВЄпЦЦВВВВЄп(ц(6│рВВпЄ▐@ ПЪ|├ЦЦ(УApplying linear algebra to number-sequences and counting-problems.
Application 1: Could the sequence 1,2,5,14,41,Е satisfy a first-order difference equation? That is, is there some single operator that annihilates it?
No: Let f(0)=1, f(1)=2, f(2)=5, etc., and suppose AT+BI annihilates the sequence f(0),f(1),f(2),Е . Then we must have
Af(1)+Bf(0)=0, Af(2)+Bf(1) = 0, etc. The first two equations become 2A+1B=0 and 5A+2B=0. Е They imply A=B=0. Why? Е The determinant of
[2 1]
[5 2]
is non-zero.
Linear algebra can give us positive information too.
Application 2: Suppose we suspect that the sequence 1, 2, 5, 13, 34, Е consisting of every other Fibonacci number satisfies a second-order linear recurrence. How might we guess it? If AT^2+BT+CI annihilates the sequence, we must have (A)(5)+(B)(2)+(C)(1) = 0 and
(A)(13)+(B)(5)+(C)(2) = 0 and (A)(34)+(B)(13)+(C)(5) = 0. The 3-by-3 matrix
[ 5 2 1]
[13 5 2]
[34 13 5]
has determinant zero (how can we see this? Е), so there exists a non-trivial solution (infinitely many such, in fact), e.g. A=1, B=-3, C=1.
General theorem (first draft):
Let
(*) (a_d T^d + a_{d-1} T^{d-1} + ... + a_0 T^0) f = 0
be a homogeneous linear recurrence equation
with constant coefficients.
Let p(t) = a_d t^d + a_{d-1} t^{d-1} + ... + a_0 ,
so that we can daringly write (*) as p(T)(f)=0.
Suppose p(t) has (how many? ... d)
distinct (real or complex) roots r_1,...,r_d.
Then the general solution to (*) is of the form
f(n) = A_d r_d^n + ... A_d r_d^n.
(Proof idea: Use partial fractions decomposition.)
(Alternative, after-the-fact logic:
Verify that each primitive solution f(n) = r^n
is a solution to (*).
Then show that these d functions are linearly independent.
Hence they span the d-dimensional space of solutions to (*).)
Note that even if the terms of the sequence are integers,
the numbers r_i and A_i need not be.
WeТve already seen this with BinetТs formula for
the Fibonacci sequence (remind them what this is).
Another Example: p(t)=t^2+1, with roots i and Цi.
The recurrence T^2 f + f = 0
means f(n+2)=-f(n) for all n,
with general solution a,b,-a,-b,a,b,-a,-b,...
(does this remind you of anything? ... the homework).
E.g., 2,0,-2,0,2,0,-2,0,..., given by f(n) = i^n+(-i)^n.
Application 2, continued: HereТs a good way to think about the every-other-Fibonnaci-number sequence. F_n = Ar^n + Bs^n, where r = (1+sqrt(5))/2 and s = (1-sqrt(5))/2. So G_n = F_{2n} = Ar^(2n) + Bs^(2n) = A(r^2)^n + B(s^2)^n. So the governing roots are r^2 = (3+sqrt(5))/2 and s^2 = (3-sqrt(5))/2, which are the roots of the quadratic equation t^2-3t+1=0.
Application 3: Find a formula for G_n,
where G_n = F_1 + F_2 + F_3 + ... + F_n:
1,3,6,11,19,...
(or reduce it to a problem of solving for a small number
of undetermined coefficients).
Applying T-I to G_n gives F_{n+1},
and applying T^2-T-I to that gives 0,
so (T-I)(T^2-T-I)=(T^3-2T^2+I) annihilates G.
As before, G_n can be written in the form
A F_n + B F_{n-1} + C.
But what if the polynomial doesnТt have distinct roots?
Test-case: p(t)=(t-1)^2=t^2-2+1, p(T)=T^2-2T+1.
WilfТs approach still applies:
We get a two-parameter family of solutions,
with generating functions (ax+b)/(x^2-2x+1).
Put a=-1 and b=1:
(1-x)/(1-2x+x^2) = 1/(1-x) = 1+x+x^2+...
(thatТs the solution we already knew about).
To find another solution, put a=1 and b=0:
x/(1-2x+x^2) = x/(1-x)^2 = x(1-x)^{-2} = x + 2x^2 + 3x^3 + ...
(check that this is what the binomial theorem gives, too)
So our two fundamental solutions here are f(n)=1 and f(n)=n.
Note: The sequence of Fibonacci numbers is annihilated by
the operator ... T^2-T-I, and the generating function has denominator equal to ...1-x-x^2. There is a correspondence here, but the exponents go in the opposite direction from one another.
In general, if p(T)=(T-rI)^d, the d fundamental solutions are
the sequences f(n)=n^k r^n for k=0 through d-1.
(When r=1, these fundamental solutions are just monomials,
and the general solution is a polynomial of degree fПа┘°∙CqЫ▓│ы:fУе╬√&eа▌▐╒╓D╖╕ы!JhЬ╝╜■4E}░▄L¤√√√√√√√√√
c╧ ё $
H
w
Н
╚
AfЧ╩№7eЫ╘╒=>fПа┘°∙C¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤√¤¤¤¤¤¤¤¤¤¤¤¤CqЫ▓│ы:fУе╬√&eа▌▐╒╓D╖╕ы!Jh¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤hЬ╝╜■4E}░▄LkБЮ╓Ўў2jkwx╕╟╫ш0¤¤¤¤¤¤¤∙¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤Д╨LkБЮ╓Ўў2jkwx╕╟╫ш0LSfx}Ч╠═√5jЧ┴╬┌х*+@AefxyС╒=Viг╙╘BВй╠°"$=VWfgЗ▒╤╥ь %FefФХну°*+,№·T0LSfx}Ч╠═√5jЧ┴╬┌х*+@AefxyС╒¤¤¤∙∙ў¤¤¤¤¤¤¤¤¤¤¤ї¤¤¤¤¤¤¤¤¤¤Д╨=Viг╙╘BВй╠°"$=VWfgЗ▒╤╥ь %F¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤FefФХну°*+,¤¤¤¤¤¤¤¤¤¤
░╨/ ░р=!░"░#Ра$Ра%░
[(@ё (NormalCJ mH ,@, Heading 3$@&00 Heading 4$@&6Б<A@Є б<Default Paragraph Font*B@Є* Body Text6Б(U@в( Hyperlink>*B*8V@в8FollowedHyperlink>*B*,4 ,╧ Ch0F,L,UW[]dfjlЪбжн╝┴СЪъЇbefiчъыюЪЭ╓┘┌▀цщъяsvMPUXГКЫдЄєM`╚╠╬╧ ) < ? B F I M Z ` r v В Е С Ф Ы Ю ▌ у ў √ `
c
l
o
К
Н
Z`|Эа!БЕо┤┬╩+
1
Ї
¤
эя'*+.ADEH╙╓ЁєFIJM▄▀befiВЕЖЙем░│╛╔HOfkХШм│▌рЇ√=@VY\a
$'=@hk▓╡
GJПТ. James Propp/C:\WINDOWS\TEMP\AutoRecovery save of Sept16.asdJames Propp/C:\WINDOWS\TEMP\AutoRecovery save of Sept16.asdJames Propp3C:\WINDOWS\Desktop\Teaching\491\Lectures\Sept16.docJames Propp3C:\WINDOWS\Desktop\Teaching\491\Lectures\Sept16.docJames Propp/C:\WINDOWS\TEMP\AutoRecovery save of Sept16.asdJames Propp3C:\WINDOWS\Desktop\Teaching\491\Lectures\Sept16.docJames Propp3C:\WINDOWS\Desktop\Teaching\491\Lectures\Sept16.docJames Propp3C:\WINDOWS\Desktop\Teaching\491\Lectures\Sept18.docJames Propp/C:\WINDOWS\TEMP\AutoRecovery save of Sept18.asdJames Propp3C:\WINDOWS\Desktop\Teaching\491\Lectures\Sept18.docFЮ ╠x`1кfЮх ■K╜1 vё>є|h ╓╥?bы<А г"YB H\ ╡wkт$ьХ ¤рl █Aаn X=x ДhДШ■╞hOJQJo(╖ЁД╨Д0¤╞╨o(()ДhДШ■╞hOJQJo(╖ЁД╨Д0¤╞╨o(()Д╨Д0¤╞╨o(()ДhДШ■╞hOJQJo(╪ЁДhДШ■╞ho(()Д╨Д0¤╞╨o(()ДhДШ■╞ho(.ДhДШ■╞hOJQJo(╖ЁДhДШ■╞hOJQJo(╖Ё╓╥?╡wk╠x`1█Aаn■K╜1FЮX=xH\¤рlvё>г"YB @АffЬndff,`@GРЗ: Times New Roman5РАSymbol3&РЗ: Arial;РАWingdings"qИ╨hїБYcДyFюg/$е└┤┤А0dВ <C:\Program Files\Microsoft Office\Templates\sixteenpoint.dotFormal power seriesJames ProppJames Propp■
рЕЯЄ∙OhлС+'│┘0tИРм╕╠╪Ї
0<
HT\dlфFormal power seriesormJames Proppamesixteenpoint.dotesJames Propp26eMicrosoft Word 8.0@b▐И'@6"ж>┴@┌НaЪ|├юg■
╒═╒Ь.УЧ+,∙оD╒═╒Ь.УЧ+,∙оPhpМФЬдм┤╝─
╠ьфUW Math Department/ВjFormal power seriesTitleШ 6>
_PID_GUIDфAN{D6192561-AA77-11D5-A227-C7476C1BAA7B}
■ !"#$■ &'()*+,■ ./01234■ ¤ 7■ ■ ■ Root Entry └FрФЗШ|├ щЯЪ|├9А1Table ─WordDocument 4SummaryInformation( %DocumentSummaryInformation8 -CompObj jObjectPool щЯЪ|├ щЯЪ|├ ■ ■
└FMicrosoft Word Document
MSWordDocWord.Document.8Ї9▓q