Discrete Mathematics for Computer Science

556 CHAPTER 9 Recurrence Relations

Since T(k) = f(k), replace the reference to T on the right-hand side of the equation,

getting

n

T(n) c'- -kf(k) + E cn-lf(1)

I=n-k+l

n

- L cn-^1 f(l)

l=n-k

Proof By induction, show that

n

T(n) = -cn-f(l)

l=k

Let no = k. Let T = {n E N : n > k and T(n) is a solution).

(Base step) First, show that

n

T cn-lf(1)

l=k

is a solution for n = k so that k E T.

k

Y ck-lfl) = ck-kf(k) = f(k) = T(k)

I=k

(Inductive step) Now, assume that T(n) is given by this expression for n > no, that is,

T(n) = _,-k cn-f(1). Now prove that T(n + 1) is also given by this expression: In this

case, prove that T(n + 1) = Z___+ cn-f(1).

T(n + 1) = cT(n) + f(n + 1) (Definition of recurrence relation)

n

= cY cn-f(l) + f(n + 1) (Inductive hypothesis)

l=k

n

= cn-'+'f(1) + f(n + 1)

l=k

n+1

= _cn+tl-f(1)

l=k

This proves n + 1 E T.

By the Principle of Mathematical Induction, T = In E N : n > k}. U

Corollary 1. The solution of

T(n) = JT(n-l)+f(n) forn>O

If (O) forn = O

is T(n) = y-n 1 f(k)