184
Recursion, Recurrence Relations, and Analysis of Algorithms
Table 3.2
To Solve Recurrence Relations of the Form S(n) ∙ cS(n ∙ 1) ∙ g(n) Subject to basis S(1)
Method
Steps
Expand, guess, verify
1. Repeatedly use the recurrence relation until you can guess a pattern.
2. Decide what that pattern will be when n − k = 1.
3. Verify the resulting formula by induction.
Solution formula
1. Match your recurrence relation to the form
S(n) = cS(n − 1) + g(n) to find c and g(n).
2. Use c, g(n), and S(1) in the formula
S(n) = c
n−1
S(1) + ∙
n
i=2
c
n−i
g(i )
3. Evaluate the resulting summation to get the final expression.
eXaMPle 17
Find a closed-form solution to the recurrence relation
S(n) = 2S(n − 1) + 3 for n ≥ 2
subject to the basis step
S(1) = 4
We’ll use the solution formula method. Comparing our recurrence relation
S(n) = 2S(n − 1) + 3
with the general form S(n) = cS(n − 1) + g(n), we see that
c = 2
g(n) = 3
The fact that g(n) = 3 says that g has a constant value of 3 no matter what the value
of its argument; in particular, g(i) = 3. Substituting into the general solution form
S(n) = c
n−1
S(1) + ∙
n
i=2
c
n−i
g(i)
we get
S(n) = 2
n−1
(4) + ∙
n
i=2
2
n−i
(3)
= 2
n−1
(2
2
) + 3 ∙
n
i=2
2
n−i
= 2
n+1
+ 332
n−2
+ 2
n−3
+ c + 2
1
+ 2
0
4
= 2
n+1
+ 332
n−1
− 1 4
(from Example 15, Section 2.2)