Section 3.2 Recurrence Relations
185
So the value of S(5), for example, is 2
6
+ 3(2
4
− 1) = 64 + 3(15) = 109.
Alternatively, by the expand, guess, and verify technique, we expand
S(n) = 2S(n − 1) + 3
= 2[2S(n − 2) + 3] + 3 = 2
2
S(n − 2) + 2 # 3 + 3
= 2
2
[2S(n − 3) + 3] + 2 # 3 + 3 = 2
3
S(n − 3) + 2
2 # 3 + 2 # 3 + 3
(
The general pattern seems to be
S(n) = 2
k
S(n − k) + 2
k−1 # 3 + 2
k−2 # 3 + c + 2
2 # 3 + 2 # 3 + 3
which, when n − k = 1 or k = n − 1, becomes
S(n) = 2
n−1
S(1) + 2
n−2 # 3 + 2
n−3 # 3 + c + 2
2 # 3 + 2 # 3 + 3
= 2
n−1
(4) + 3[2
n−2
+ 2
n−3
+ c + 2
2
+ 2 + 1]
= 2
n+1
+ 3[2
n−1
− 1]
(from Example 15, Section 2.2)
Finally, we must prove by induction that S(n) = 2
n+1
+ 3[2
n−1
− 1].
Base case: n = 1: S(1) = 4 = 2
2
+ 3[2
0
− 1], true
Assume S(k) = 2
k+1
+ 3[2
k−1
− 1]
Show S(k + 1) = 2
k+2
+ 3[2
k
− 1]
S(k + 1) = 2S(k) + 3
(by the recurrence relation)
= 2(2
k+1
+ 3[2
k−1
− 1]) + 3
(by the inductive hypothesis)
= 2
k+2
+ 3 # 2
k
− 6 + 3
(multiplying out)
= 2
k+2
+ 3[2
k
− 1]
Practice 12
Rework Practice 11 using Equation (8).
■
example 18
Find a closed−form solution to the recurrence relation
T(n) = T(n − 1) + (n + 1) for n ≥ 2
subject to the basis step
T(1) = 2
Using the solution formula method and comparing the recurrence relation
with the general form from Equation (6), S(n) = cS(n − 1) + g(n), we find
that c = 1 and g(n) = n + 1. We’ll substitute into the solution equation (8)
S(n) = c
n−1
S(1) + ∙
n
i=2
c
n−i
g(i), where g(i) will be i + 1.
remInDer
When expanding, be sure
to pick up all the pieces
of the recurrence relation
recipe, like the + 3 in this
example.