420
Relations, Functions, and Matrices
and this equation in turn, using property 11 of the logarithm function (see
Appendix C), can be written as
S(n) = n
log b a
S(1) + n
c
∙
m−1
i=0
a
a
b
c b
i
(5)
We’ll see the expression log b a frequently, so we’ll temporarily give it a simpler
name: Let w = log b a. Then, expanding the summation, Equation (5) can be
written as
S(n) = n
w
S(1) + n
c
c1 + a
a
b
c b + a
a
b
c b
2
+ c + a
a
b
c b
m−1
d
We can see that the expression in brackets represents the sum of the first m terms
of a geometric sequence with first term equal to 1 and common ratio r equal to
(a∙b
c
). If r ∙ 1, this sum (see Exercise 27 in Section 2. 2) has the value
1 − a
a
b
c b
m
1 − a
a
b
c b
and
S(n) = n
w
S(1) + n
c
≥
1 − a
a
b
c b
m
1 − a
a
b
c b
¥
(6)
The condition r ∙ 1 means (a∙b
c
) ∙ 1 or a ∙ b
c
. This means that Equation (6)
holds for both Case 1 and Case 3 of the master theorem, so to prove those cases
we’ll do some tiresome algebra on Equation (6).
First, note that
n
c
a
a
b
c b
m
= n
c
a
a
b
c b
log b n
=
n
c
a
log b n
b
c log b n
=
n
c
n
log b a
b
log b n
c
=
n
c
n
log b a
n
c
= n
log b a
= n
w
so Equation (6) becomes
S(n) = n
w
S(1) +
n
c
− n
c
a
a
b
c b
m
b
c
− a
b
c
= n
w
S(1) +
b
c
(n
c
− n
w
)
b
c
− a
or
S(n) = n
w
S(1) +
b
c
b
c
− a
n
c
+
b
c
a − b
c n
w
(7)