Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

116 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6

EXAMPLE 6.12 Consider the following homogeneous recurrence relation:

an= 6 an− 1 − 9 an− 2

The characteristic polynomial
(x)follows:

(x)=x^2 − 6 x+ 9 =(x− 3 )^2

Thus
(x)has only the one rootr 0 =3. Now we use Theorem 6.9 to obtain the following general solution of
the recurrence relation:

an=c 13 n+c 2 n 3 n

Thus any values forc 1 andc 2 will give a solution to the recurrence relation.
Suppose we are also given the initial conditionsa 1 =3,a 2 =27. Using the recurrence relation we can
compute the next few terms of the sequence:

3 , 27 , 135 , 567 , 2187 , 8109 , ...

The unique solution is obtained by findingc 1 andc 2 using the initial conditions. Specifically:

Forn=1 anda 1 = 3 , we get: c 131 +c 2 ( 1 )( 3 )^1 =3or3c 1 + 3 c 2 = 3

Forn=2 anda 2 = 27 , we get: c 132 +c 2 ( 2 )( 3 )^2 =27 or 9c 1 + 18 c 2 = 27

Solving the system of the two equations in the unknownsc 1 andc 2 yields:

c 1 =−1 and c 2 = 2

Thus the following is the unique solution of the recurrence relation with the given initial conditions:

an=− 3 n+ 2 n 3 n= 3 n( 2 n− 1 )

6.9Solving General Homogeneous Linear Recurrence Relations

Consider now a general linear homogeneouskth-order recurrence relation with constant coefficients which
has the form

an=C 1 an− 1 +C 2 an− 2 +C 3 an− 3 +···+Ckan−k=

∑k

i= 1

Cian− 1 (6.1)

whereC 1 ,C 2 ,...,Ckare constants withCk=0. Thecharacteristic polynomial
(x)of the recurrence relation
(6.1) follows:

(x)=xk−C 1 xk−^1 −C 2 xk−^2 −C 3 xk−^3 −···−Ck=xk−

∑k

i= 1

C 1 xk−^1

The roots of
(x)are called thecharacteristic rootsof the recurrence relation.
The following remarks are in order.

Remark 1: Ifp(n)andq(n)are solutions of (6.1), then any linear combination

c 1 p(n)+c 2 q(n)

ofp(n)andq(n)is also a solution. (This is not true if the recurrence relation is nonhomogeneous.)