advertisement

Lecture on Recurrence Relations I A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form an = c1 an−1 + c2 an−2 + · · · + ck an−k where c1 , . . . ck are real numbers and ck 6= 0. k = 1: f (n) = 5f (n − 1). k = 2: f (n) = f (n − 1) + f (n − 2). This is not of any degree: f (n) = f (1) + f (2) + · · · + f (n − 1). For degree 1 recurrences: f (n) = rf (n − 1) – This is the major part of the sequence. All solutions look like f (n) = Crn . C is determined by the initial value. So we say that f (n) = Crn is the general solution of the recurrence. Example 1. Solve the recurrence f (n) = 7f (n − 1) with f (0) = 4. How about “Solve the recurrence with f (1) = 14? “ For degree 2 Not obvious. But we have a theorem. Theorem 1. Let c1 and c2 be real numbers. Suppose that r2 − c1 r − c2 = 0 has two distinct roots r1 and r2 . Then the sequence {an } is a solution of the recurrence relation an = c1 an−1 c2 an−2 if and only if an = α1 r1n + α2 r2n for n = 0, 1, 2, . . . , where α1 and α2 are constants. This suggests the following way to solve a second order recurrence. Given a recurrence an = c1 an−1 + c2 an−2 , 1. Write down the characteristic equation r2 − c1 r − c2 = 0, and find two roots r1 and r2 . 2. If r1 6= r2 , Then the general solution is an = α1 r1n + α2 r2n . 3. If there are initial values, we find α1 and α2 explicitly. Example 2. What is the solution of the recurrence an = an−1 + 2an−2 with a0 = 2 and a1 = 7? Solution. The characteristic equation is r2 − r − 2 = 0, which has two roots r! = 2 and r2 = −1. Hence an is of the form α1 2n + α2 (−1)n . From the initial conditions, it follows that a0 = 2 = α1 + α2 a1 = 7 = α1 · 2 + α2 · (−1) Solving these two equations yields that α1 = 3 and α2 = −1. Hence an = 3 · 2n − (−1)n . Example 3. The Fibonacci Sequence F (1) = f (2) = 1, and F (n) = F (n − 1) + F (n − 2). 1 One can extend to F (0) = 0. √ √ The characteristic equation: r2 −r−1 = 0. It has two roots r1 = (1+ 5)/2 and r2 = (1− 5)/2. Hence √ !n √ !n 1− 5 1+ 5 + α2 F (n) = α1 2 2 Use F (0) = 0 and F (1) = 1, (Also all right to use F (2) = 1), we have α1 + α2 = 0, √ ! √ ! 1+ 5 1− 5 α1 + α2 = 1. 2 2 √ √ The solution is α1 = 1/ 5, α2 = −1/ 5. Hence √ !n √ !n 1 1+ 5 1 1− 5 F (n) = √ −√ 2 2 5 5 Note: It is a closed formula. But even not obvious that such a number is an integer. Most properties of the Fibonacci sequence still need ”induction“. What if the characteristic equation has a double root? Answer: In that case, the general solution is of the form an = α1 rn + α2 nrn . Example 4. Solve the recurrence an = 6an−1 − 9an−2 with initial values a0 = 1 and a1 = 6? Solution. The characteristic equation is r2 − 6r + 9 = 0. It has a double root r1 = r2 = 3. The general solution is of the form an = α1 · 3n + α2 · n3n . Using the initial condition, we get a0 = 1 = α1 , a1 = 6 = α1 · 3 + α2 · (1)(3) Hence α1 = α2 = 1. And an = 3n + n3n . 2