Task: Soving Recurrence Relations

Part 1. Homogeneous linear 2nd degree relations with constant coe cients.
Consider the recurrence relation
( ) T(n) + aT(n - 1) + bT (n - 2) = 0
This is called a homogeneous linear 2nd degree recurrence relation with constant coe cients:
2nd degree because it gives T(n) in terms of T(n - 1) and T(n - 2),
linear and constant coe cients because of the form of the left side, and
homogeneous because of the zero on the right hand side.
The idea for solving this relation is to \guess" a solution of the form T(n) = xn for some
number x, and then to simply substitute this expression into the equation to determine the
value(s) of x that work. Since T(n - 1) = xn-1 and T(n - 2) = xn-2 we get the equation
xn + axn-1 + bxn-2 = 0
Since x is clearly not zero, we can divide by xn-2 to get
x2 + ax + b = 0
which is called the characteristic equation for the recurrence relation ( ).

Case 1: If this equation factors as (x-r1)(x-r2) = 0 with r1 6= r2 (so that the characteristic
equation has two distinct roots), then the general solution to ( ) is
T(n) = c1(r1)n + c2(r2)n
where c1 and c2 are constants. This is called a general solution because every function T(n)
that is a solution to the relation ( ) has this form. If we also have initial conditions T(0) = t0
and T(1) = t1 then we can determine the values of c1 and c2 and thus get the exact formula
for T(n). We'll illustrate the process with a typical example.

Example 1. Solve the recurrence relation
T(n) - 4T(n - 1) + 3T(n - 2) = 0; T(0) = 0; T(1) = 2
Note: This could also be written as

                                    0                                  n=0

T(n) = {     2                   n=1

                                    4T(n - 1) - 3T(n - 2)      n > 1

Solution: The characteristic equation is x2 - 4x + 3 = 0, or (x - 3)(x - 1) = 0, so the
general solution is T(n) = c13n + c21n = c13n + c2. To nd c1 and c2 we plug in the initial
conditions to get two equations in those two variables:
0 = T(0) = c130 + c2 = c1 + c2
2 = T(1) = c131 + c2 = 3c1 + c2


It's easy to solve these equations for the solution c1 = 1, c2 = -1, so the nal answer is
T(n) = 3n - 1
Check: We can check our answer quickly and easily. The recurrence formula gives us
T(2) = 4T(1) - 3T(0) = 4(2) - 0 = 8
T(3) = 4T(2) - 3T(1) = 4(8) - 3(2) = 26
T(4) = 4T(3) - 3T(2) = 4(26) - 3(8) = 80
It appears that the sequence is indeed giving us numbers that are one less than the powers
of 3 (1, 3, 9, 27, 81, : : : ), so the formula T(n) = 3n - 1 seems to be correct.
Case 2: If the characteristic equation factors as (x - r)2 = 0 (with a single root), then we
use as our general solution the formula
T(n) = c1rn + c2nrn
As before, initial conditions can be used to solve for c1 and c2. Here is a typical example.
Example 2. Solve the recurrence relation
                                 3                                       n = 0
T(n) = {   17                                     n = 1
                                10T(n - 1) - 25T(n - 2)      n > 1


Solution: The characteristic equation is x2 - 10x + 25 = 0, or (x - 5)2 = 0, so the general
solution is T(n) = c15n + c2n5n. As before, we nd c1 and c2 by plugging in the initial
conditions:
3 = T(0) = c150 + c2(0) = c1
17 = T(1) = c151 + c2(1)51 = 5c1 + 5c2
The solution here is c1 = 3 and c2 = 2=5, so the exact solution is
T(n) = (3)5n + (2=5)n5n = (15 + 2n)5n-1
Check: The recurrence formula gives us values
T(2) = 10T(1) - 25T(0) = 10(17) - 25(3) = 95
T(3) = 10T(2) - 25T(1) = 525
These are indeed the values given by our formula as well: T(2) = (15 + 4)51 = 95, and
T(3) = (15 + 6)52 = 525.
Case 3: It can happen in general recurrence relations that the characteristic equation x2 +
ax+b = 0 has no real roots, but instead has two complex number roots. There is a method
of solution for such recurrences, but we will not concern ourselves with this case since it does
not typically arise in recurrences that come from studying recursive algorithms.