4 Linear Recurrence Relations & the Fibonacci Sequence

1 4 Linear Recurrence Relations & the Fibonacci SequenceRecall the classic example of the Fibonacci Sequence (Fn) n=1= (1, 1, 2, 3, 5, 8, 13, 21, ..), defined by{Fn+2=Fn+1+FnF1=F2=1 This Sequence has well-known Relations to population growth (famously breeding rabbits), spirals inthe center of sunflowers, etc. From a number theory perspective, we have two main questions:1. How do we find a formula for thenthFibonacci number? More generally, how do we solvelinear Recurrence Relations ?2. Does the Fibonacci Sequence satisfy any interesting patterns when we consider its remaindersmodulo an integer?}

2 Linear Recurrence RelationsThe general theory of Linear recurrences is analogous to that of Linear differential Sequence (xn) n=1satisfies alinear Recurrence relation of order r Nif there exista0, .. ,ar,fwitha0,ar6 0 such that n N,arxn+r+ar 1xn+r 1+ +a0xn=fThe definition is malleable: in particular The Sequence could start withx0, or anywhere else; The coefficientsakare generally functions, though for us they will usually beconstant; Iff 0, the Recurrence ishomogeneous; this is usually be the case for the Linear recurrencexn+1=2xn 1 with initial conditionx1=2.

3 A simpleapproach might be to list the values ofxnand try to spot a pattern:(xn) = (2, 3, 5, 9, 17, 33, 65, 129, ..)Since the ratioxn+1xnappears to be approaching 2, we might guess thatxn= 2n+ for someconstants , . Substituting this into the original Recurrence , we see that 2n+1+ = 2n+1+2 1 =2 1 =1 But thenx1=2 +1=2 =12. The solution is thereforexn=12 2n+1=2n 1+1If this ad hoc approach makes you uncomfortable, prove by induction that this really is the will give some of the discussion in the language of second-degree equations.

4 The proofs aresimple exercises, and it should be obvious how the theory extends to recurrences of other the second-order recurrenceaxn+2+bxn+1+cxn= Given initial conditionsx1,x2, there exists a unique Ifx(p)nis a fixed solution to the Recurrence , then all solutions have the formxn=x(c)n+x(p)nwherex(c)nsatisfies the associated homogeneous equationaaxn+2+bxn+1+cxn=0( )3. The solutions to( )form a two-dimensional vector space: given linearly independent solutionsynandzn, there exist unique constants , such thatxn= yn+ zn4. Ifa,b,care constant, thecharacteristic equationof( )is the quadratica 2+b +c=0.

5 Thereare two cases, dependent on the roots 1, 2:(a) If 16= 2, then the general solution isxn= n1+ n2(b) If 1= 2, then the general solution isxn= ( + n) n1ax(p)andx(c)should recall theparticular solutionandcomplementary functionfrom differential ( , mk. II).In the context of the Theorem: x(c)n= 2nis the general solution to the homogeneous relationxn+1 2xn=0 with character-istic equation 2=0. x(p)n=1 is a single solution to the full recurrencexn+1=2xn 1. The general solution isxn= 2n+1; applying the initial conditionx1=2 yields = us, the important case is the Fibonacci Sequence : the characteristic equation is 2 1=0= =1 52= , where =1+ 52is the golden ratio and =1 52= 1.

6 Choosing the constants such thatF1=F2=1, we conclude,Theorem (Binet s Formula).Fhe Fibonacci Sequence hasnthtermFn= n n 5= n ( ) n 5=1 5[(1+ 52)n (1 52)n]2 Exercises1. Solve the homogeneous Recurrence relation{xn+2 4xn+1+4xn=0x1=1,x2= 42. Find a particular solution of the formx(p)n=dn+eto the relation{xn+2 4xn+1+4xn=nx1=1,x2= 4 Using your answer to the previous question, find the general solution to the full Recurrence .(This is precisely the method of undetermined coefficients as seen in differential equations)3. Find the general solution to the Recurrence relation{xn+2 2xn+1+2xn=0x1=1,x2=0(The characteristic equation has complex roots: this is no matter!)}}}

7 If you want a challenge, write youranswer using binomial coefficients..)4. Prove all parts of Theorem (Hint: for part 3, consider wn:=xn yn znwhere( )=(y1z1y2z2) 1(x1x2)) The Fibonacci Sequence inZmIf a solution to a Recurrence relation is in integers, one can ask if there are any patterns with respectto a given modulus. It should be clear that any Recurrence of the formxn+2=axn+1+bxnwherea,b Zand with initial conditionsx1,x2 Znecessarily produces a Sequence of Fibonacci Sequence (a=b=x1=x2=1) is one of the simplest such, so we begin by huntingfor 21, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1.

8 Period 3 Fnmod 31, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, ..Period 8 Fnmod 41, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, ..Period 6 Fnmod 51, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1, ..Period 20 Fnmod 61, 1, 2, 3, 5, 2, 1, 3, 4, 1, 5, 0, 5, 5, 4, 3, 1, 4, 5, 3, 2, 5, 1, 0, 1, 1, ..Period 24 Fnmod 71, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0, 1, 1, ..Period 16 Fnmod 81, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, ..Period 12 Fnmod 91, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 0, 1, 1.

9 Period 24As soon as we see a pair of 1 s we know that the Sequence repeats. Does this always happen? Arethere any patterns in the periods? Can you guess what the period is modulo 10?3 Theorem Fibonacci Sequence inZmis is a simple box-principle argument. Let{(Fn,Fn+1):n N}be the set of pairs of consec-utive Fibonacci numbers modulom. This is a subset ofZm Zm(cardinalitym2). Since the sequenceis infinite, the box-principle tells us that at least one pair occurs infinitely many times: n,N Nsuch thatFn Fn+NandFn+1 Fn+1+N(modm)( )Since the defining Recurrence relation is second-order, the pairs(Fn,Fn+1)and(Fn+N,Fn+1+N)gener-ate thesame sequencemodulom.

10 It follows that(Fn)is eventually see that the entire Sequence is periodic, observe that we can writeFn 1=Fn+1 FnThis defines the Sequence in reverse, starting from any pair. In particular, the reverse sequencesstarting from the pairs(Fn,Fn+1)and(Fn+N,Fn+1+N)in( )are identical, whence the periodicitycontinues back to the initial pair(F1,F2).Definition byN(m)the period of the Fibonacci Sequence modulom; that is, the valueof thesmallest Nsuch thatFN+1 FN+2 1(modm).By looking for patterns in the above table, you might hypothesize some elementary +S Fk(modm), k N N(m)| For anym,nwe haveN(m)|N(mn).