Discrete Mathematics for Computer Science

564 CHAPTER 9 Recurrence Relations

Since both cl and c2 are roots of the characteristic equation of the recurrence c2- kC -

k2 = 0 and c2 - kjc 2 - k2 0. Therefore,

ac7-^2 (cj - k 1 cl - k 2 ) + Bc- 2 (c 2 - kIc 2 - k 2 ) = 0

and the conclusion follows.

To prove the converse, that is, every solution is of the form Acn + Bce for every

n E N, let no = 0 and T = {n : any solution H has the required for H(n)}.

(Base step) Assume H(0) = A + B and H(1) = Ac, + Bc 2 for some choice of A and

B. Then, 0, 1 c T.

(Inductive step) Now choose n > 2 and assume that H(0), H(1) ..... H(n - 1) have

the required form for every solution H. We know H(n) = kIH(n - 1) + k 2 H(n - 2). By

the inductive hypothesis both H (n - 1) and H (n - 2) have the required form, so we sub-

stitute these terms and simplify the algebra:

H(n) = kl(Ac'-^1 + Bcn-^1 ) + k 2 (Ac7-^2 + Bxn-^2 )

= Acn-z(kici + k 2 ) + Bc-^2 (kic 2 + k 2 )

Since cl and C2 are solutions of the complementary equation, we have c2 - klc^1 -

0 and c 2= -k2 k, C2 = -0and k2 = c2 0. Substituting the values for c^2 2 and c2for c2 kici+ k^2 and

ki c 2 + k 2 , we get

H(n) = -• t1 n-2 c c1^2 + ÷~2 Bc^2 Cc2^2

= Ac' + Bck

as required and n E T.

By the Strong Form of Mathematical Induction we conclude that T = N. N

Theorem 2. (Solution of Second-Order Recurrence Relations) The general solu-

tion of an = klan-1 + k2an-2, where n > 2 with kj and k 2 as constants and k 2 :A 0, is

an = Ac' + Bc' when the recurrence relation has distinct roots cl and C2 for its character-

istic equation. Each assignment of particular values to A and B gives rise to a particular

solution of the recurrence.

In the case discussed here, the characteristic equation has two nonequal roots. The

function H has a slightly different form when the two roots are equal.

9.4.2 Solving the Fibonacci Recurrence

Using Theorem 1, the general solution of the Fibonacci recurrence is given by

Fn = A )+B

,

where A and B are arbitrary constants and n > 0. It remains to determine values for A and

B so that Fn is given directly as a function of n. This can be done by using the two boundary

values for the recurrence relation to determine two linear equations in the unknowns A and

B. The boundary values of the Fibonacci recurrence are given for n = 0, 1. The system of

equations resulting is