Linear Recurrences Example 7.49: The Fibonacci Numbers are the numbers in the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... and can be defined by the linear recurrence relation fu+2 = fut1 + fu for all n 2 0, with the initial conditions fo = 1 and f1 = 1. Example 7.50: Find /100- Instead of using the recurrence to compute fim. we'd like to find a formula for f. that holds for all 7 2 0. Definition 7.51: A sequence of numbers To, I1, 72, Ty, .. . is defined recursively if each number in the sequence is determined by the numbers that occur before it in the sequence. A linear recurrence of length it has the form Inth = Inthi+02: 1 2+ +01, n20, for some real numbers a1, 02, . . .; (x. Example 7.52: The simplest linear recurrences have length one, so have the form Intl = 0In for n 2 0, with a E R and some initial value In- In this case, Therefore, In = ("To- Example 7.53: Find a formula for I, if In+2 = 21241 + 3x,, for n 2 0, with zo = 0 and I, = 1. Solution. Define Vn = In for each n 2 0 . Ther and for n > 0, Now express Va+1 = as a matrix product: This is a linear dynamical system, so we can apply the techniques used earlier, provided that A is diagonalizable. ca(x) = det(x] - A) = =3 2 =13 - 2x -3 = (x -3)(z + 1). Therefore A has eigenvalues My = 3 and My = -1, and is diagonalizable. X1=3 is a basic eigenvector corresponding to do = 3. and Xz = ] is a basic eigerivector corresponding to 12 = -1. Furthermore P = [ X X2 ] = 3 1 is invertible and is a diagonalizing matrix for A, and P-AP = D= [8 4] Writing PV = by . we get Therefore, V. = =6, A7 X, +ba Ag Xz =13- [3 ] +4(1- [7].and So = Example 7.54: Solve the recurrence relation It+2 = 57241 - 621, k 20 with zo = 0 and $1 = 1. Solution. Write It+2 = 5Ik+1 - 6:k Next, find the eigenvalues and corresponding basic eigenvectors for A = - 6 A has eigenvalues ), = 2 with corresponding eigenvector X = and do = 3 with corresponding eigerivector X = P= [2 3 ].P = [3 7] and Finally. V= Ikti = biXX, + beAX = (-1)28 2 +3* [ 3 ] and therefore Exercise Solve the recurrence relation with zo = 1 and I1 = 1. Answer 1 = 1 (3 +1 - (-2)*+1). Exercise Best Or1 Consider the recurrence relation Th+2 = 20k+1 + 831, k 20, with zo = U and I, = 1. Find Is. T. =