192
Recursion, Recurrence Relations, and Analysis of Algorithms
—and then substitute in the second equation to solve for q:
[S(1) − q]r 1 + qr 2 = S(2)
q(r 2 − r 1 ) = S(2) − S(1)r 1
q =
S(2) − S(1)r 1
r 2 − r 1
Now what happens if the characteristic equation t
2
− c 1 t − c 2 = 0 happens
to have one repeated root, that is, r 1 = r 2 ? Oops—we can’t solve this system of
equations. The solution form when the characteristic equation has a repeated root
r looks like
S(n) = pr
n−1
+ q(n − 1)r 
n−1
for all n ≥ 1
where p and q satisfy the equations
p = S(1)
pr + qr = S(2)
This can be proved by induction in a manner similar to the distinct roots case
(see Exercise 44).
example 22
Solve the recurrence relation
S(n) = 8S(n − 1) − 16S(n − 2) for n ≥ 3
subject to the initial conditions
S(1) = 1
S(2) = 12
In this recurrence relation, c 1 = 8 and c 2 = −16. To find the closed-form solution,
we form the characteristic equation
t
2
− 8t + 16 = 0
(t − 4)
2
= 0
which has a repeated root r = 4. The solution is
S(n) = p4
n−1
+ q(n − 1)4
n−1
where
p = 1
p(4) + q(4) = 12
Solving this system of equations, p = 1 and q = 2, so the solution is
S(n) = 4
n−1
+ 2(n − 1)4
n−1
= (2n − 1)4
n−1