WIXLIB

1 Basic definitions3recurrence with two parameters. Once the parameters and the initialvalues are given, the whole sequence—that is, its future values—iscompletely determined. But, also, if the parameters and two consecutive values are given, all the past (and future) values are completelydetermined.B.Special Lucas sequencesI shall repeatedly consider special Lucas sequences, which are important historically and for their own sake. These are the sequencesof Fibonacci numbers, of Lucas numbers, of Pell numbers, and othersequences of numbers associated to binomials.(a) Let P 1, Q 1, so D 5. The numbers Un Un (1, 1)are called the Fibonacci numbers, while the numbers Vn Vn (1, 1)are called the Lucas numbers. Here are the initial terms of thesesequences:Fibonacci numbers : 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .Lucas numbers: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 99, 322, . . .(b) Let P 2, Q 1, so D 8. The numbers Un Un (2, 1)and Vn Vn (2, 1) are the Pell numbers and the companion Pellnumbers. Here are the first few terms of these sequences:Un (2, 1): 0, 1, 2, 5, 12, 29, 70, 169, . . .Vn (2, 1): 2, 2, 6, 14, 34, 82, 198, 478, . . .(c) Let a, b be integers such that a b 1. Let P a b, Q ab,n bnso D (a b)2 . For each n 0, let Un a a band Vn an bn .Then it is easy to verify that U0 0, U1 1, V0 2, V1 a b P ,and (Un )n 0 , (Vn )n 0 are the first and second Lucas sequences withparameters P , Q.In particular, if b 1, one obtains the sequences of numbers Un an 1na 1 , Vn a 1; now the parameters are P a 1, Q a.Finally, if also a 2, one gets Un 2n 1, Vn 2n 1, and nowthe parameters are P 3, Q 2.C.GeneralizationsAt this point, it is appropriate to indicate extensions of the notionof Lucas sequences which, however, will not be discussed in thislecture. Such generalizations are possible in four directions, namely,

41. The Fibonacci Numbers and the Arctic Oceanby changing the initial values, by mixing two Lucas sequences, bynot demanding that the numbers in the sequences be integers, or byhaving more than two parameters.Even though many results about Lucas sequences have been extended successfully to these more general sequences, and have foundinteresting applications, for the sake of definiteness I have opted torestrict my attention only to Lucas sequences.(a) Let P , Q be integers, as before. Let T0 , T1 be any integers suchthat T0 or T1 is non-zero (to exclude the trivial case). LetW0 P T0 2T1andW1 2QT0 P T1 .LetTn P · Tn 1 Q · Tn 2Wn P · Wn 1 Q · Wn 2and(for n 2).The sequences (Tn (P, Q))n 0 and Wn (P, Q))n 0 are the (first andthe second) linear recurrence sequences with parameters (P, Q) andassociated to the pair (T0 , T1 ). The Lucas sequences are special, normalized, linear recurrence sequences with the given parameters; theyare associated to (0, 1).(b) Lehmer (1930) considered the following sequences. Let P , Q be2non-zero integers, α, β the roots of the polynomial X P · X Q,and defineLn (P, Q) nα βn if n is odd, if n is even.α βαn β nα2 β 2L (Ln (P, Q))n 0 is the Lehmer sequence with parameters P , Q.Its elements are integers. These sequences have been studied byLehmer and subsequently by Schinzel and Stewart in severalpapers which also deal with Lucas sequences and are quoted in thebibliography.(c) Let R be an integral domain which need not be Z. Let P , Q R,P , Q 0, such that D P 2 4Q 0. The sequences (Un (P, Q))n 0 ,(Vn (P, Q))n 0 of elements of R may be defined as for the case whenR Z.Noteworthy cases are when R is the ring of integers of a numberfield (for example, a quadratic number field), or R Z[x] (or other

2 Basic properties5polynomial ring), or R is a finite field. For this latter situation, seeSelmer (1966).(d) Let P0 , P1 , . . . , Pk 1 (with k 1) be given integers, usuallysubjected to some restrictions to exclude trivial cases. Let S0 , S1 ,. . . , Sk 1 be given integers. For n k, define:Sn P0 · Sn 1 P1 · Sn 2 P2 · Sn 3 . . . ( 1)k 1 Pk 1 · Sn k .Then (Sn )n 0 is called a linear recurrence sequence of order k, withparameters P0 , P1 , . . . , Pk 1 and initial values S0 , S1 , . . . , Sk 1 .The case when k 2 was seen above. For k 1, one obtains thegeometric progression (S0 · P0n )n 0 .There is great interest and still much to be done in the theory oflinear recurrence sequences of order greater than 2.2Basic propertiesThe numbers in Lucas sequences satisfy many, many properties thatreflect the regularity in generating these numbers.A.Binet’s formulasBinet (1843) indicated the following expression in terms of the rootsα, β of the polynomial X 2 P X Q:(2.1) Binet’s formulas:Un αn β n, Vn αn β n .α βThe proof is, of course, very easy. Note that by Binet’s formulas,Un ( P, Q) ( 1)n 1 Un (P, Q)andnVn ( P, Q) ( 1) Vn (P, Q).So, for many of the following considerations, it will be assumed thatP 1.B.Degenerate Lucas sequencesLet (P, Q) be such that the ratio η α/β of roots of X 2 P x Qis a root of unity. Then the sequences U (P, Q), V (P, Q) are said tobe degenerate.

61. The Fibonacci Numbers and the Arctic OceanNow I describe all degenerate sequences. SinceP 2 2Qα β βαQη η 1 is an algebraic integer and rational, it is an integer. From αβ αβ 2it follows P 2 2Q 0, Q, 2Q, and this gives P 2 Q, 2Q, 3Q,4Q. If gcd(P, Q) 1, then (P, Q) (1, 1), ( 1, 1), (2, 1), or ( 2, 1),and the sequences areU (1, 1) :U ( 1, 1) :V (1, 1) :V ( 1, 1) :U (2, 1) :U ( 2, 1) :V (2, 1) :V ( 2, 1) : 1,1, 1, 1,4, 4,2,2,0,1,1,0,0,1, 1,0,2,1, 1, 2,2, 1, 1,2,0,1,2,3,0,1, 2,3,2,2,2,2,2, 2,2, 2, 1,0,1,1,0, . . . 1,0, . . .1,2,1, 1, 2, . . . 1,2, . . .5,6,7, . . .5, 6,7, . . .2,2,2, . . . 2,2, 2, . . .From the discussion, if the sequence is degenerate, then D 0 orD 3.C.Growth and numerical calculationsFirst, I note results about the growth of the sequence U (P, Q).(2.2) If the sequences U (P, Q), V (P, Q) are non-degenerate, then Un , Vn tend to infinity (as n tends to ).This follows from a result of Mahler (1935) on the growth ofcoefficients of Taylor series. Mahler also showed(2.3) If Q 2, gcd(P, Q) 1, D 0, then, for every ε 0 and nsufficiently large, Un β n 1 ε .The calculations of Un , Vn may be performed as follows. Let M Then for n 1, UnUn 1P1 Q0 . M n 110

2 Basic propertiesand VnVn 1 Mn 12P7 .To compute a power M k of the matrix M , the quickest method is toecompute successively the powers M , M 2 , M 4 , . . . , M 2 where 2e k 2e 1 ; this is done by successively squaring the matrices. Next, ifthe 2-adic development of k is k k0 k1 2 k2 22 . . . ke 2e ,ewhere ki 0 or 1, then M k M k0 (M 2 )k1 . . . (M 2 )ke .Note that the only factors actually appearing are those where ki 1.Binet’s formulas allow also, in some cases, a quick calculation of Unand Vn .If D 5 and β 1, then αn 1 Un 2D(for n 1),and Vn αn 12 (for n such that n · ( log β ) log 2). Hence,ncUn is the closest integer to αD , and Vn is the closest integer to αn .This applies in particularto Fibonacci and Lucas numbers for which D 5, α (1 5)/2 1.616 . . . , (the golden number), β (1 5)/2 0.616 . . . .It follows that the Fibonacci number Un and the Lucas number Vnhave approximately n/5 digits.D.Algebraic relationsThe numbers in Lucas sequences satisfy many properties. A look atthe issues of The Fibonacci Quarterly will leave the impression thatthere is no bound to the imagination of mathematicians whose endeavor it is to produce newer forms of these identities and properties.Thus, there are identities involving only the numbers Un , in othersonly the numbers Vn appear, while others combine the numbers Unand Vn . There are formulas for Um n , Um n , Vm n , Vm n (in termsof Um , Un , Vm , Vn ); these are the addition and subtraction formulas.There are also formulas for Ukn , Vkn , and Unk , Vnk , Unk , cVnk (wherek 1) and many more.I shall select a small number of formulas that I consider mostuseful. Their proofs are almost always simple exercises, either byapplying Binet’s formulas or by induction.

81. The Fibonacci Numbers and the Arctic OceanIt is also convenient to extend the Lucas sequences to negativeindices in such a way that the same recursion (with the givenparameters P, Q) still holds.(2.4) Extension to negative indices:U n 11Un , V n n VnnQQ(for n 1).(2.5) Un and Vn may be expressed in terms of P , Q. For example,Un P n 1 ( 1)kn 2n 3P n 3 Q P n 5 Q2 . . .12n 1 kP n 1 2k Qk · · · (last summand)kwhere n nn 2 ( 1) 2 1P Q 2 1n 1(last summand) 2 n 1n 1 22( 1)Qif n is even,if n is odd.Thus, Un fn (P, Q), where fn (X, Y ) Z[X, Y ]. The function fn isisobaric of weight n 1, where X has weight 1 and Y has weight 2.Similarly, Vn gn (P, Q), where gn Z[X, Y ]. The function gn isisobaric of weight n, where X has weight 1, and Y has weight 2.(2.6) Quadratic relations:Vn2 DUn2 4Qnfor every n Z.This may also be put in the form:2 P Un 1 Un QUn2 Qn .Un 1(2.7) Conversion formulas:DUn Vn 1 QVn 1 ,Vn Un 1 QUn 1 ,for every n Z.

2 Basic properties9(2.8) Addition of indices:Um n Um Vn Qn Um n ,Vm n Vm Vn Qn Vm n DUm Un Qn Vm n ,for all m, n Z.Other formulas of the same kind are:2Um n Um Vn Un Vm ,2Q Um n Um Vn Un Vm ,nfor all m, n Z.(2.9) Multiplication of indices:U2n Un Vn ,V2n Vn2 2Qn ,U3n Un (Vn2 Qn ) Un (DUn2 3Qn ),V3n Vn (Vn2 3Qn ),for every n Z.More generally, if k 3 it is possible to find by induction on kformulas for Ukn and Vkn , but I shall refrain from giving themexplicitly.E.Divisibility properties(2.10) Let Um 1. Then, Um divides Un if and only if m n.Let Vm 1. Then, Vm divides Vn if and only if m n and n/m isodd.For the next properties, it will be assumed that gcd(P, Q) 1.(2.11) gcd(Um , Un ) Ud , where d gcd(m, n).(2.12) Vdgcd(Vm , Vn ) nmand are odd,dd1 or 2 otherwise,where d gcd(m, n).if

101. The Fibonacci Numbers and the Arctic Ocean(2.13) Vdgcd(Um , Vn ) mnis even, is odd,dd1 or 2 otherwise,ifwhere d gcd(m, n).(2.14) If n 1, then gcd(Un , Q) 1 and gcd(Vn , Q) 1.3 Prime divisors of Lucas sequencesThe classical results about prime divisors of terms of Lucas sen bnquences date back to Euler, (for numbers a a b), to Lucas (forFibonacci and Lucas numbers), and to Carmichael (for other Lucassequences).A.The sets P(U ), P(V ), and the rank of appearance.Let P denote the set of all prime numbers. Given the Lucas sequencesU (Un (P, Q))n 0 , V (Vn (P, Q))n 0 , letP(U ) {p P n 1 such that Un 0 and p Un },P(V ) {p P n 1 such that Vn 0 and p Vn }.If U , V are degenerate, then P(U ), P(V ) are easily determined sets.Therefore, it will be assumed henceforth that U , V are nondegenerate and thus, Un (P, Q) 0, Vn (P, Q) 0 for all n 1.Note that if p is a prime dividing both p, q, then p Un (P, Q),p Vn (P, Q), for all n 2. So, for the considerations which willfollow, there is no harm in assuming that gcd(P, Q) 1. So, (P, Q)belongs to the setS {(P, Q) P 1, gcd(P, Q) 1, P 2 Q, 2Q, 3Q, 4Q}.For each prime p, defineρU (p) ρV (p) nif n is the smallest positive index where p Un , if p Un for every n 0,nif n is the smallest positive index where p Vn , if p Vn for every n 0.

3 Prime divisors of Lucas sequences11We call ρU (n) (respectively ρV (p))) is called the rank of appearanceof p in the Lucas sequence U (respectively V ).First, I consider the determination of even numbers in the Lucassequences.(3.1) Let n 0. Then:Un even andVn even P even P odd P even P oddQ odd, n even,orQ odd, 3 n,Q odd, n 0,orQ odd, 3 n.Special Cases. For the sequences of Fibonacci and Lucas numbers(P 1, Q 1), one has:Un is even if and only if 3 n,Vn is even if and only if 3 n. b, Vn an bn , with a For the sequences of numbers Un a a bb 1, gcd(a, b) 1, p a b, q ab, one has:If a, b are odd, then Un is even if and only if n is even, while Vn iseven for every n.If a, b have different parity, then Un , Vn are always odd (for n 1).nnWith the notations and terminology introduced above the result(3.1) may be rephrased in the following way:(3.2) 2 P(U ) if and only if Q is odd 2ρU (2) 3 if P even, Q odd,if P odd,Q odd,if P odd,Q even,2 P(V ) if and only if Q is odd 1ρV (2) 3if P even, Q odd,if P odd, if P odd,Q odd,Q even.

121. The Fibonacci Numbers and the Arctic OceanMoreover, if Q is odd, then 2 Un (respectively 2 Vn ) if and only ifρU (2) n (respectively ρV (2) n).This last result extends to odd primes:(3.3) Let p be an odd prime.If p P(U ), then p Un if and only if ρU (p) n.If p P(V ), then p Vn if and only if ρV (p) n andnρV (p)is odd.Now I consider odd primes p and indicate when p P(U ).(3.4) Let p be an odd prime.If p P and p Q, then p Un for every n 1.If p P and p Q, then p Un if and only if n is even.If p P Q and p D, then p Un if and only if p n.DIf p P QD, then p divides UψD (p) where ψD (p) p ( Dp ) and ( p )denotes the Legendre symbol.Thus,P(U ) {p P p Q},so P(U ) is an infinite set.The more interesting assertion concerns the case where p P QD,the other ones being very easy to establish.The result may be expressed in terms of the rank of appearance:(3.5) Let p be an odd prime.If p P , p Q, then ρU (p) .If p P , p Q, then ρU (p) 2.If p P Q, p D, then ρU (p) p.If p P QD, then ρU (p) ΨD (p).Special Cases. For the sequences of Fibonacci numbers (P 1,Q 1), D 5 and 5 Un if and only if 5 n.If p is an odd prime, p 5, then p Up ( 5 ) , so ρU (p) (p ( p5 )).Because U3 2, it follows that P(U ) P.p bLet a b 1, gcd(a, b), P a b, Q ab, Un a a b.If p divides a or b but not both a, b, then p Un for all n 1.If p ab, p a b, then p Un if and only if n is even.If p ab(a b) but p a b, then p Un if and only if p n.If p ab(a b)(a b), then p Up 1 . (Note that D (a b)2 ).nThus, P(U ) {p : p ab}.n

3 Prime divisors of Lucas sequences13Taking b 1, if p a, then p Up 1 , hence p ap 1 1 (this isFermat’s Little Theorem, which is therefore a special case of the lastassertion of (3.4)); it is trivial if p (a 1)(a 1).The result (3.4) is completed with the so-called law of repetition,first discovered by Lucas for the Fibonacci numbers:(3.6) Let pe (with e 1) be the exact power of p dividing Un . Letf 1, p k. Then, pe f divides Unkpf . Moreover, if p Q, pe 2,then pe f is the exact power of p dividing Unkpe .It was seen above that Fermat’s Little Theorem is a special case ofthe assertion that if p is a prime and p P QD, then p divides UΨD (p) .I indicate now how to reinterpret Euler’s classical theorem.If α, β are the roots of the characteristic polynomial X 2 P X Q,define the symbol α, β2 1 if Q is even,0 if Q is odd, P is even, 1 if Q is odd, P is odd,and for any odd prime p α, βp Dif p D, if p D.p0Let Ψα,β (p) p ( α,βp ) for every prime p. Thus, using the previousnotation, Ψα,β (p) ΨD (p) when p is odd and p D.For n p pe , define the generalized Euler functionΨα,β (n) nrΨα,β (p),pso Ψα,β (pe ) pe 1 Ψα,β (p) for each prime p and e 1. Define alsothe Carmichael function λα,β (n) lcm{Ψα,β (pe )}. Thus, λα,β (n)divides Ψα,β (n).In the special case where α a, β 1, and a is an integer,then Ψa,1 (p) p 1 for each prime p not dividing a. Hence, ifgcd(a, n) 1, then Ψa,1 (n) ϕ(n), where ϕ denotes the classicalEuler function.The generalization of Euler’s theorem by Carmichael is thefollowing:

141. The Fibonacci Numbers and the Arctic Ocean(3.7) n divides Uλα,β (n) hence, also, UΨα,β (n) .(p)It is an interesting question to evaluate the quotient ΨρUD(p). It wasshown by Jarden (1958) that for the sequence of Fibonacci numbers,p ( p5 )sup ρU (D) (as p tends to ). More generally, Kiss (1978) showed:(3.8) (a) For each Lucas sequence Un (P, Q), ΨD (p)supρU (p) .(b) There exists C 0 (depending on P , Q) such thatpΨD (p) C.ρU (p)log pNow I turn my attention to the companion Lucas sequence V (Vn (P, Q))n 0 and I study the set of primes P(V ). It is not knownhow to describe explicitly, by means of finitely many congruences,the set P(V ). I shall indicate partial congruence conditions that arecomplemented by density results.Because U2n Un Vn , it then follows that P(V ) P(U ). It wasalready stated that 2 P(V ) if and only if Q is odd.(3.9) Let p be an odd prime.If p P , p Q, then p Vn for all n 1.If p P , p Q, then p Vn if and only if n is odd.If p P Q, p D, then p Vn for all n 1.If p P QD, then p V 1 ΨD (p) if and only if ( QP ) 1.2D 1If p P QD and ( Qp ) 1, ( p ) ( p ), then p Vn for all n 1.The above result implies that P(V ) is an infinite set. One may further refine the last two assertions; however, a complete determinationof P(V ) is not known.In terms of the rank of appearance, (3.9) can be rephrased asfollows: This was extended by Ward (1954) for all binary linear recurrences

3 Prime divisors of Lucas sequences15(3.10) Let p be an odd prime.If p P , p Q, then ρV (p) 1.If p P , p Q, then ρV (p) .If p P Q, p D, then ρV (p) .1If p P QD, ( Qp ) 1, then ρV (p) divides 2 ΨD (p).D 1If p P QD, ( Qp ) 1, ( p ) ( p ), then ρV (p) .The following conjecture has not yet been established in general,but has been verified in special cases, described below:Conjecture. For each companion Lucas sequence V , the limitδ(V ) limπV (x)π(x)exists and is strictly greater than 0.Here, π(x) #{p P p x} and πV (x) #{p P(V ) p x}.The limit δ(V ) is the density of the set of prime divisors of V amongall primes.Special Cases. Let (P, Q) (1, 1), so V is the sequence of Lucasnumbers. Then the above results may be somewhat completed. Explicitly:If p 3, 7, 11, 19 (mod 20), then p P(V ).If p 13, 17 (mod 20), then p / P(V ).If p 1, 9 (mod 20) it may happen that p P(V ) or that p / P(V ).Jarden (1958) showed that there exist infinitely many primes p 1 (mod 20) in P(V ) and also infinitely many primes p 1 (mod 20)not in P(V ). Further results were obtained by Ward (1961) who

Fibonacci numbers and similar sequences. Like the icebergs in the Arctic Ocean, the sequence of Fibonacci numbers is the most visible part of a theory which goes deep: the theory of linear recurring sequences. The so-called Fibonacci numbers appeared in the solution of a problem by F