CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 117
Remark 2: Ifris a root of multiplicitymof the characteristic polynomial(x)of (6.1), then each of the
following
rn,nrn,n^2 rn,...,nn−^1 rnis a solution of (6.1). Thus any linear combination
c 1 rn+c 2 nrn+c 3 n^2 rn+···+cmnm−^1 rn=(c 1 +c 2 n+c 3 n^2 +···+cmnm−^1 )rnis also a solution.
EXAMPLE 6.13 Consider the following third-order homogeneous recurrence relation:
an= 11 an− 1 − 39 an− 2 + 45 an− 3The characteristic polynomial(x)of the recurrence relation follows:
(x)=x^3 − 11 x^2 + 39 x− 45 =(x− 3 )^2 (x− 5 )Thus(x)has two roots,r 1 =3 of multiplicity 2 andr 2 =5 of multiplicity 1. Thus, by the above remarks, the
following is the general solution of the recurrence relation:
an=c 1 ( 3 n)+c 2 n( 3 n)+c 3 ( 5 n)=(c 1 +c 2 n)( 3 n)+c 3 ( 5 n)Thus any values forc 1 ,c 2 ,c 3 will give a solution to the recurrence relation.
Suppose we are also given the initial conditionsa 0 =5,a 1 =11,a 3 =25. Using the recurrence relation we
can compute the next few terms of the sequence:
5 , 11 , 25 , 71 , 301 , 1667 , ...The unique solution is obtained by findingc 1 ,c 2 ,c 3 using the initial conditions. Specifically:
Forn=0 anda 0 = 5 , we get: c 1 +c 3 = 5
Forn=1 anda 1 = 11 , we get: 3 c 1 + 3 c 2 + 5 c 3 = 11
Forn=2 anda 2 = 25 , we get: 9 c 1 + 18 c 2 + 25 c 3 = 25Solving the system of the three equations in the unknownsc 1 ,c 2 ,c 3 yields:
c 1 = 4 ,c 2 =− 2 ,c 3 = 1Thus the following is the unique solution of the recurrence relation with the given initial conditions:
an=( 4 − 2 n)( 3 n)+ 5 nRemark: Finding the roots of the characteristic polynomial(x)is an important step in solving recurrence
relations. Generally speaking, this may be difficult when the degree of(x)is greater than 2. (Example B.16
indicates one way to find the roots of some polynomials of degree 3 or more.)