Discrete Mathematics for Computer Science

562 CHAPTER 9 Recurrence Relations

values one at a time, starting with F 2 .As an example, F 5 may be calculated using this

procedure as follows:

F 2 = FI + F 0 = I + I = 2

F 3 = F 2 + Fl =2+ = 3

F 4 = F 3 + F 2 = 3+ 2 = 5

F 5 = F 4 + F 3 = 5+ 3=8

Although it is always possible to determine any value of a recurrence relation by building

up values of the recurrence relation from the initial values, finding a function of n that can

be evaluated to calculate directly the value of the recurrence at n is more interesting.

9.4.1 Second Order-Recurrence Relations

The definition of such notions as solution and initial values given for first-order recurrence

relations generalize naturally to second-order recurrence relations. The method for solv-

ing second-order recurrence relations that is presented here generalizes to higher-order

recurrence relations, but we will not deal with the general theory for nth-order recurrence

relations. The recurrence relations to be solved are of the form

an = klan-I + k2an-2 for n > 2

where kl and k 2 are arbitrary constants with k 2 0 0 and ai is shorthand for a (i) for i =

0,1,2 ..... This recurrence relation is second order, because the recurrence relation is

defined in terms of the two preceding terms and no other terms. By writing the recurrence as

an - klan-1 - k2an-2 = 0

we see that the function on the right-hand side is the zero function. Consequently, the

recurrence relation is homogeneous. A second-order recurrence relation will require two

boundary values or initial values to evaluate the terms needed to determine a value for an.

By examining a class of first-order recurrence relations, it is possible to gain an in-

sight regarding the form of a function that will be a solution to a second-order recurrence

relation. Consider the first-order recurrence relation

a ban-I forn> 1

an = for n = 0

Using back substitution, we find the solution to be the function an = bn. The feature to

focus on in this case is that the solution for each n is of the form bn, a constant raised to the

nth power. In the case of a second-order recurrence relation, it would be nice if the solution

were some combination of two different such functions, since this would be a natural gen-

eralization of the result for first-order recurrence relations. At this point, however, we have

no reason to expect that this will be the case. Proceeding on the basis that the solution is of

this form may lead to a contradiction. On the other hand, if we proceed on the assumption

that the solution is of this form and no contradiction is found, then an insight regarding

how such recurrence relations can be solved may be found.

As an example, let us suppose a solution for the Fibonacci recurrence is a function

of the form a, = c' for some c and then see what this implies. By substituting the values

of an for n, n - 1, and n - 2 into the Fibonacci recurrence, more information about this