Section 3.2 Recurrence Relations
197
example 26
Solve the recurrence relation
T(1) = 3
T(n) = 2T a
n
2
b + 2n
This is a match for Equation (16), where c = 2 and g(n) = 2n. Therefore
g(2
i
) = 2(2
i
). Substituting into Equation (21)—the solution of Equation (16)—
gives the following result, where we use the fact that 2
log n
= n.
T(n) = 2
log n
T(1) + ∙
log n
i=1
2
log n−i
2(2
i
)
= 2
log n
(3) + ∙
log n
i=1
2
log n+1
= n(3) + (2
log n+1
)log n
= 3n + (2
log n # 2)log n
= 3n + 2n log n
Practice 15
Show that the solution to the recurrence relation
S(1) = 1
S(n) = 2Sa
n
2
b + 1 for n ≥ 2, n = 2
m
is 2n − 1. (Hint: See Example 15 in Section 2.2 and note that 2
log n
= n.)
■
exercISeS 3.2
In Exercises 1–12, solve the recurrence relation subject to the basis step.
1. S(1) = 5
S(n) = S(n − 1) + 5 for n ≥ 2
2. B(1) = 5
B(n) = 3B(n − 1) for n ≥ 2
S e c t I o n 3 . 2 Review
technIQueS
• Solve recurrence relations by the expand, guess,
and verify technique.
• Solve linear, first-order recurrence relations with
constant coefficients by using a solution formula.
• Solve linear, second-order homogeneous recurrence
relations with constant coefficients by using the
characteristic equation.
• Solve divide-and-conquer recurrence relations by
using a solution formula.
maIn IDea
• Certain recurrence relations have closed-form
solutions.
W
W