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

114 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6

6.8 SOLVING SECOND-ORDER HOMOGENEOUS LINEAR RECURRENCE RELATIONS

Consider a homogeneous second-order recurrence relation with constant coefficients which has the form

an=san− 1 +tan− 2 or an−san− 1 −tan− 2 = 0

wheresandtare constants witht=0. We associate the following quadratic polynomial with the above recurrence
relation:

(x)=x^2 −sx−t

This polynomial
(x)is called thecharacteristic polynomialof the recurrence relation, and the roots of
(x)
are called itscharacteristic roots.

Theorem 6.8: Suppose the characteristic polynomial
(x)=x^2 −sx−tof the recurrence relation

an=san− 1 +tan− 2

has distinct rootsr 1 andr 2. Then the general solution of the recurrence relation follows, where

c 1 andc 2 are arbitrary constants:

an=c 1 r 1 n+c 2 r 2 n

We emphasize that the constantsc 1 andc 2 may be uniquely computed using initial conditions. We note that
the theorem is true even when the roots are not real. Such cases lie beyond the scope of this text.

EXAMPLE 6.10 Consider the following homogeneous recurrence relation:

an= 2 an− 1 + 3 an− 2

The general solution is obtained by first finding its characteristic polynomial
(x)and its rootsr 1 andr 2 :

(x)=x^2 − 2 x− 3 =(x− 3 )(x+ 1 ); rootsr 1 = 3 ,r 2 =− 1

Since the roots are distinct, we can use Theorem 6.8 to obtain the general solution:

an=c 13 n+c 2 (− 1 )n

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

1 , 2 , 8 , 28 , 100 , 356 , 1268 , 3516 , ...

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

Forn=0 anda 0 = 1 ,we get: c 130 +c 2 (− 1 )^0 =1orc 1 +c 2 = 1

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

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

c 1 =

3

4

and c 2 =

1

4

Thus the following is the unique solution of the given recurrence relation with the given initial conditionsa 0 =1,
a=2:

an=

3

4

3 n+

1

4

(− 1 )n=

3 n+^1 +(− 1 )n

4