SECTION 2.1 Elementary Number Theory 93
2.1.9 Linear recurrence relations
Many, if not most reasonably serious students have heard of theFi-
bonacci sequence^22 the first few terms of which are
1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 ,...
Even one who hasn’t had much exposure to mathematics can easily
guess the successive term in the sequence given the previous two terms
as it is clear that this term is the sum of the previous two terms. Put
more mathematically, ifun denotes the n-th term, then one has the
linear difference equation
un+2=un+1+un, n= 1, 2 ,..., u 0 = 1, u 1 = 1.More elementary sequences come from the familiararithmeticand
geometricsequences. Arithmetic sequences are generated by differ-
ence equations of the form un+1 = un+d, n = 0, 1 , 2 ,..., where d
is a constant. Geometric sequences come from the difference equation
un+1 =kun, n= 0, 1 , 2 ,.... The general term for the arithmetic and
geometric sequences can be easily solved for in terms ofu 0 :
Arithmetic:un+1=un+d, n= 1, 2 ,...=⇒un=u 0 +nd.Geometric: un+1=kun, n= 1, 2 ,...=⇒un=knu 0.The above three difference equations are linear in the sense that
none of the unknown termsunoccur to powers other than 1. A very fa-
mous nonlinear recurrence relation is the so-calledlogistic recurrence
equation(or “Logistic map”), given by a relation of the form
un+1=k(1−un)un, n= 0, 1 , 2 ,....(^22) which made a cameo appearance in the movie,The Da Vinci Code.