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? 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.}

2 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. 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.

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. 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.

4 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! 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.}}}

5 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, ..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, ..Period 24As soon as we see a pair of 1 s we know that the Sequence repeats.

6 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. 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).

7 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).3. Ifgcd(m,n) =1thenN(mn) =lcm(N(m),N(n)). The( )direction is trivial. The( )is just the division algorithm: there exist uniqueq,r Zsuch thatS=qN(m) +r,0 r<N(m)from which the minimality ofN(m)forcesr= For anyk,m,n, we haveFk+N(mn) Fk(modmn) = Fk+N(mn) Fk(modm)By part 1, we conclude thatN(m)|N(mn).3. When gcd(m,n) =1, observeFk+N Fk(modmn) {Fk+N Fk(modm)and,Fk+N Fk(modn)Suppose this holds for allk. By definitionN=N(mn)is the least positive integer satisfying theLHS. By part 2, lcm(N(m),N(n))is the least positive integer satisfying the , even for such a simple Sequence , the periodN(m)is not fully (pn) =pn 1N(p)whenpis prime: no counter-example has been found amongall primesp< this, one could, for example, computeN(2304) =N(28 32) =lcm(27N(2), 3N(3)) =lcm(128 3, 3 8) =384 Binet s formula modulopFor roughly half the primes, we can obtain a modular version of Binet s a prime congruent to either 1 or 4 modulo 5 (equivalentlyp 1 mod 10),then c Z psuch that n N,Fn c 1[(1+c2)n (1 c2)n](modp) idea is to look for a valuecthat plays the role of 5: otherwise said, we wantc2 5modulop.}

8 Computing Legendre symbols and recalling quadratic reciprocity, we see that(5p)= ( 1)5 12 p 12(p5)=(p5)=1 The congruencec2 5 therefore has a solution, which we may assume is odd, for otherwise we couldchoose the other solutionp c. Now define the sequenceJn c 1[(1+c2)n (1 c2)n](modp)It is easily checked thatJn Jn 1+Jn 2andJ1 J2 1, whenceJn is easy to see that1 c2are both non-zero modulop, so we always get both terms in Binet s , thenc2 5 c2 16 c 4. We choosec=7, which yieldsc 1 8. ThereforeFn 8(4n 8n) 3(8n 4n) (mod 11)Binet s formula gives us more: by Fermat s Little Theorem,Fn+10 3(8n+10 4n+10) 3(8n 4n) Fn(mod 11)whence the periodN(11)divides 10. This is true in general..Theorem a prime congruent to either 1 or 4 modulo 5. ThenN(p)|p :=1+c2and :=1 c2to obtainFn+(p 1)k c 1[ n (p 1)k n (p 1)k] c 1[ n n] Fn(modp)since , 6 0. By Theorem , we concludeN(p)|p is harder to prove, but the following can also be shown: Ifp 2, 3 modulo 5, thenN(p)|2p+2.

9 We shouldn t expect a discrete version of Binet sformula since there are no valuescwhich satisfyc2 5. N(m){=6mifm=2 5kfor somek 1 4motherwiseOther Recurrence Relations : Lucas SequencesIt is reasonable to ask if the solution toanylinear constant coefficient Recurrence relation is periodicmodulom. Suppose that the Recurrence has orderrand thatxn+r+ar 1xn+r 1+ +a1xn+1+a0xn=0hasintegercoefficientsak. By considering ther-tuples(xN,xN+1, .. ,xN+r 1)modulomand applying the box-principle argument of Theorem , we see that any solution isthereforeeventually periodicmodulom: with a trivial modification, the gcd result (Theorem ) alsoholds. We don t necessarily get full periodicity however, for example{xn+1=2xnx1=1= (xn) (1, 2, 0, 0, 0, 0, 0, 0, 0, ..) (mod 4)To obtain full periodicity, it is enough thata0be a unit generalizations of the Fibonacci Sequence are important in number theory.}}

10 In particular:Definition Sequence (xn)is a solution to the recurrencexn+2=Pxn+1 Qxn, wherePandQare given integers. It is typical to start these sequences fromx0and to consider two indepen-dent solutions U(P,Q)satisfies(x0,x1) = (0, 1) V(P,Q)satisfies(x0,x1) = (2,P)The Fibonacci Sequence is thereforeU(1, 1). In line with the above discussion, these sequences areeventually periodic modulomand the gcd theorem for periods also holds. Most examples seem tosatisfyN(pk) =pk 1N(p), although counter-examples are known (Exercise ).6 Example Lucas sequencesU(2, 1)andV(2, 1)are known, respectively, as thePellnumbersandPell-Lucas we write the first few,Un+1=2Un+Un 1,U0=0,U1=1Vn+1=2Vn+Vn 1,V0=2,V1=2n0 1 234567Un(2, 1)0 1 2512 2970169Vn(2, 1)2 2 6 14 34 82 198 478you should start to see the pattern: the ratio12 VnUn=pnqnis the Sequence of convergents of the continuedfraction 2= [1, 2, 2, 2, 2, 2.]