Section 3.2 Recurrence Relations
195
Assume that C(k) = 1 + log k. Then
C(2k) = 1+ C(k)
(by the recurrence relation)
= 1 + 1 + log k
(by the inductive hypothesis)
= 1 + log 2 + log k
(log 2 = 1)
= 1 + log 2k
(property of logarithms)
This calculation completes the inductive proof.
We’d like to find a closed-form solution for (16) subject to the basis that S(1)
is known. We could use the expand, guess, and verify approach to find the general
solution, but instead we will do a transformation on (16) to convert it to a firstorder recurrence relation with constant coefficients, use the solution formula we
already have for such a recurrence relation, and then reverse the transformation.
Figure 3.2 shows this round-about approach.
Equation (16) assumes that n = 2
m
with n ≥ 2. From this it follows that
m = log n and m ≥ 1. Substituting 2
m
for n in equation (16) results in
S(2
m
) = cS(2
m−1
) + g(2
m
)
(17)
Now, letting T(m) represent S(2
m
) in Equation (17), we get
T(m) = cT(m − 1) + g(2
m
) for m ≥ 1
(18)
Equation (18) is a linear, first-order equation with constant coefficients; from
Equation (8), we obtain the solution
T(m) = c
m−1
T(1) + ∙
m
i=2
c
m−i
g(2
i
)
(19)
subject to the basis condition that T(l) is known. Because Equation (18) holds for
m = 1, we know that
T(1) = cT(0) + g(2)
Figure 3.2
B. First-order
recurrence relation,
constant coeffcients
Solution to B
Solution to A
A. Divide & conquer
recurrence relation