Discrete Mathematics for Computer Science

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 indica-

tion 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 -. 6 (2n + 1). n .(n + 1)

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