Discrete Mathematics for Computer Science

Fibonacci Recurrence Relation 563

possibility can be determined. For example, it may be possible to determine whether such

a function can even be a solution:

a. - an-1 - an-2 = 0

Cn -2Cn-1 -2Cn-2 = o

cn-2 (C -- C -- 1) = 0

Since the product of two real numbers-namely, C0-^2 and c^2 - c - 1-is zero, either

Cn-2 =0 or c^2 -c- 1 =0. If Cn-2 =0, then c=Oand an =Ofor alln > 0. This so-

lution, called the zero function, is the trivial solution of the recurrence relation. For a

homogeneous recurrence relation, the zero function is always a solution. Since the primary

interest is in nontrivial solutions, suppose c A 0, which implies that c^2 - c - 1 = 0. This

equation is called the characteristic equation of the recurrence relation. The roots of this

equation are

C --

2 2

This discussion began by asking if the nontrivial solutions of a second-order ho-

mogeneous recurrence relation have a form similar to the nontrivial solution of a first-

order homogeneous recurrence relation. By trying such a function, we found that if a

second-order homogeneous recurrence relation had such a nontrivial solution, then the

two possible constants that had the property were the solutions to the characteristic equa-

tion of the recurrence relation. Now, we prove that not only these two functions but also

any linear combination of two such functions are solutions of the recurrence relation. Much

like the previous discussion of back substitution, a conjecture about the form of a solution

has been found, and we must now prove that such functions really are solutions. It is be-

yond the scope of this text to prove the fundamental result that no other nontrivial solutions

of a second-order homogeneous recurrence relation exist. We will therefore just state the

result.

Theorem 1. Let a, = klan-1 ± k2an-2 for n > 2. Suppose the characteristic equa-

tion of this recurrence relation has distinct roots cl and c2. Any function of the form

H(n) = Acln + Bc 2 n, where A and B are arbitrary constants, is a solution of this re-

currence relation.

Proof. To verify that a function of the form H(n) is a solution, write with all terms on the

left-side of the equal sign and then substitute H (n) for some value of n into the recurrence
relation, giving

an - klan-1 - k2an-2 =

H(n) - k1H(n - 1) - k 2 H(n - 2) =

Ac + BC B k + Bc') - k 2 (Acn-

(^2) + Bcn- (^2) ) =
a(c' - c -1kc - kn-2) + B(cn 2 - kcj--^1 - kzckn-2) =
Acn-2 (c2 -- klCl -- k2) -+- Bcn-2(c2 - klC2^2 -^2 k2)