Section 3.2 Recurrence Relations
181
example 15
Consider again the basis step and recurrence relation for the sequence S of
Example 1:
S(1) = 2
(4)
S(n) = 2S(n − 1) for n ≥ 2
(5)
Let’s pretend we don’t already know the closed-form solution and use the expand,
guess, and verify approach to find it. Beginning with S(n), we expand by using the
recurrence relation repeatedly. Keep in mind that the recurrence relation is a recipe
that says S at any value can be replaced by two times S at the previous value. We
apply this recipe to S at the values n, n − 1, n − 2, and so on:
S(n) = 2S(n − 1)
= 2[2S(n − 2)] = 2
2
S(n − 2)
= 2
2
[2S(n − 3)] = 2
3
S(n − 3)
By looking at the developing pattern, we guess that after k such expansions, the
equation has the form
S(n) = 2
k
S(n − k)
This expansion of S values in terms of lower S values must stop when n − k = 1,
that is, when k = n − 1. At that point,
S(n) = 2
n−1
S[n − (n − 1)]
= 2
n−1
S(l) = 2
n−1
(2) = 2
n
which expresses the closed-form solution.
We are not yet done, however, because we guessed at the general pattern.
We now confirm our closed-form solution by induction on the value of n. The
statement we want to prove is therefore S(n) = 2
n
for n ≥ 1.
For the basis step, S(l) = 2
1
. This is true by equation (4). We assume that
S(k) = 2
k
. Then
S(k + 1) = 2S(k)
(by equation (5))
= 2(2
k
)
(by the inductive hypothesis)
= 2
k+1
This proves that our closed-form solution is correct.
■
PRaCtiCe 11 Find a closed-form solution for the recurrence relation, subject to the basis step, for
sequence T:
1. T(l) = 1
2. T(n) = T(n − 1) + 3 for n ≥ 2
(Hint: Expand, guess, and verify.)
remInDer
Don’t get hung up on “n”
and “n − 1” in the recurrence relation. Think of it
as “S at some value is 2
times S at the previous
value.”