188
Recursion, Recurrence Relations, and Analysis of Algorithms
Linear Second-Order Recurrence Relations
In a first-order recurrence relation, the nth term depends only on the previous
term. In a second-order recurrence relation, the nth term depends on the two
previous terms. Linear second-order homogeneous recurrence relations with constant coefficients therefore have the form
S(n) = c 1 S(n − 1) + c 2 S(n − 2)
(9)
The Fibonacci sequence is an example (Exercise 37 asks for a solution):
F(1) = 1
F(2) = 1
F(n) = F(n − 1) + F(n − 2) for n > 2
example 20
Not every recurrence relation fits the pattern of Equation (6). Consider the recurrence relation
T(1) = 1
T(n) = 2nT(n − 1) for n ≥ 2
Although this is a linear, first-order recurrence relation, it does not have constant
coefficients. Equation (8) does not apply. To find a closed-form solution, we have
to go back to the expand, guess, and verify technique.
T(n) = 2nT(n − 1)
= 2n 32(n − 1)T(n − 2) 4 = 2
2
n(n − 1)T(n − 2)
= 2
2
n(n − 1) 32(n − 2)T(n − 3) 4 = 2
3
n(n − 1)(n − 2)T(n − 3)
In general, it seems that
T(n) = 2
k
n(n − 1)(n − 2) … (n − (k − 1))T(n − k)
When n − k = 1, then k = n − 1 and
T(n) = 2
n−1
n(n − 1)(n − 2) … (2)T(1) = 2
n−1
n(n − 1)(n − 2) … (2)(1) = 2
n−1
n!
This is our guess at a closed-form solution, which we verify by induction on n.
Base case, T(1): T(1) = 2
1−1
1! = 2
0
(1) = 1, true
Assume T(k):
T(k) = 2
k−1
k!
Show T(k + 1): T(k + 1) = 2
k
(k + 1)!
T(k + 1) = 2(k + 1)T(k)
(by the recurrence relation)
= 2(k + 1)2
k−1
k!
(by the inductive hypothesis)
= 2
k
(k + 1)!
Therefore our closed-form solution guess was correct.