Solving First-Order Recurrence Relations
557
Proof In the general formula, let c = 1 and k = 0.
0
Corollary 2. The solution of
T(n)=cT(n-1)+d forn > 0
forn = 0
where c and d are real numbers and c # 1 is
Cn+1
T(n) = d.
c--1
Proof In the general formula, let f(n) = d for n > 0 and k = 0. The sum becomes
n
T(n) = d. Z ck
k=O
Cn+
1 - 1
=d.
c--1
When c is not equal to 1 in the general formula and the function f(n) is a constant for
all n > k for some k, the solution becomes the sum of a finite geometric series.
In the case f(n) is not a constant, a wide range of functions exist for which Y n=o f(k)
is known, but the answers often entail using more complicated summing techniques than
those presented here. Examples using Theorem 2 and its corollaries will give some indication of the problems that can be solved using this result.
Example 1. Solve
T (n)=o(n - 1)+n2 forn > 1
for n =0
Solution. In the general formula, f(n) = n
2 for n > 0, c = 1, and k - 0. Since T(0) =
f(0), by Corollary 1 the solution is
T(n)=
I
2
-.
(2n + 1). n . (n + 1)
6
l=l
See Theorem 9(b) in Section 7.10 for a derivation of this formula.
U
Example 2. Solve
T(n)
•3T(n-1)+4 forn > 1
1f~ 4
for n = 0
Solution. In the general formula, f(n) = 4 for n > 0, c = 3, and k = 0. By Corollary 2,
the solution is
3nl+1 - 1
T(n) = 4 3n-1 -- 2 .(3n+1 - 1)
3- 1