Discrete Mathematics for Computer Science

554 CHAPTER 9 Recurrence Relations

Proof Letn 0 =l.LetT={n eN:T(n)=2n-1}.

(Base step) First, show that the conclusion holds for n = 1. T(l) = 1 = 21 - 1 There-

fore, for n = 1, the formula gives the correct value for T(1) and 1 E T.

(Inductive step) Let n > no. Assume that T(n) = 2n - 1 is a solution, and show for

n + 1 that T(n + 1) = 2n+1 - 1 is a solution:

T(n + 1) = 2T (n) + 1 Definition of recurrence relation

= 2(2n - 1) + 1 Induction hypothesis

= 2n+1 - 1

Therefore, n + 1 E T.

By the Principle of Mathematical Induction, T(n) = 2n - 1 for n > 1. U

After analysis of this sort, a knowledgeable comparison of this algorithm with any

other algorithm that solves this problem can be made by comparing the functions that

represent the complexity of each solution method.

rnSolving First-Order Recurrence Relations

The method of solution used for the Tower of Hanoi recurrence relation can be used to solve

the general class of first-order recurrence relations. After formalizing the terms needed to

describe a general first-order recurrence relation, a solution method will be given.

Definition 1. A first-order recurrence relation is an expression of the form

T(n)= IcT(n-1)+f(n) forn >k

If (k) for n = k

defined for all natural numbers greater than or equal to some positive integer k where c is

a constant and f is a function of n for n = k, k + 1, k + 2 .....

The recurrence relation is of the first order, because T(n) is defined as a function

involving the value T(n - 1) but no other values T(1) where 1 < n. The value of T at

n = k is called an initial value or a boundary value. The initial value can be used to

calculate values of T (n) for increasingly larger n. For example,

T(k + 1) = cT(k) + f(k + 1)

will give T(k + 1) in terms of the known values for T(k) and f(k + 1). The boundary

value will often be the value T(0) or T(1), but it can be the value of T for any natural

number. When the boundary value is not given as the value T (0) but as T (k) for k > 0,

the recurrence relation may not be defined for values less than k. The function f can be

any function of n, but it quite often is a constant or a polynomial function of n. The more

complex the function f, the more difficult it is to put the solution of the recurrence relation

in a simple form.

It is helpful to examine the Tower of Hanoi recurrence relation again and identify all

its parts in terms of the new definitions. The recurrence relation is

T(n) =2T(n-1)+1 fornn>2

11 forn = I