Discrete Mathematics for Computer Science

566 CHAPTER 9 Recurrence Relations

For small values of n, it often is much easier to use the recurrence relation directly to

calculate values of the recurrence relation than to evaluate a complex function. The point

is that a closed form of the function can be used to calculate any term of the sequence

directly. The solution also gives a tool for directly studying properties of the recurrence

relation for large n.

9.4.3 Rules for Solving Second-Order Recurrence Relations

The procedure used to solve the Fibonacci recurrence is an application of one method for

solving a large class of second-order recurrence relations. Before doing another example,

we summarize the procedure.

Solving Second-Order Homogeneous Recurrence Relations

with Constant Coefficients Using the Complementary Equation

with Distinct Real Roots

H(n) +AH(n- 1) + BH(n- 2) = 0,

H(n 1 ) = D, and H(n 2 ) = E.

STEP 1: Assume f (n) = c" is a solution, and substitute for H (n), yielding the char-

acteristic equation

c2+ Ac + B =0

STEP 2: Find the roots of the characteristic equation: Cl and c2. Use the quadratic

formula if the equation does not factor. If cl 0 c2, then the general solution is

S(n) = Acn + Bc•

STEP 3: Use the initial conditions to form the system of equations

H(nl) = D = Acl1J + Bcn

2

H(n 2 ) = E = Acn^2 + Bcn

2

STEP 4: Solve the system of equations found in step 3, getting A 0 and B 0 as the two

solutions. Form the particular solution

H(n) = AoCln + Boc 2 n

Quite often, the boundary conditions will be the values of the recurrence at 0 and 1. All

that is required of the boundary values is that they be values of the recurrence relation given

for two different natural numbers. In the case where the boundary values are not given

for consecutive natural numbers, the domain of the recurrence relation must be specified

to include all the integer values greater than or equal to the smaller integer for which a

boundary value is given.

Example 1. Solve the recurrence relation an - 6an-1 - 7a,-2 = 0 for n > 5 where

a3 = 344 and a4 = 2400.