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

120 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6

Fig. 6-2

RECURSION

6.11. Consider the second-order homogeneous recurrence relationan=an− 1 + 2 an− 2 with initial conditions

a 0 =2,a 1 =7,

(a) Find the next three terms of the sequence.

(b) Find the general solution.

(c) Find the unique solution with the given initial conditions.

(a) Each term is the sum of the preceding term plus twice its second preceding term. Thus:

a 2 = 7 + 2 ( 2 )= 11 ,a 3 = 11 + 2 ( 7 )= 25 ,a 4 = 25 + 2 ( 11 )= 46

(b) First we find the characteristic polynomial
(t)and its roots:


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

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

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

(c) The unique solution is obtained by findingc 1 andc 2 using the initial conditions:

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

Forn= 1 ,a 1 = 7 ,we get: c 1 ( 21 )+c 2 (− 1 )^1 =7or2c 1 −c 2 = 7

Solving the two equations forc 1 andc 2 yieldsc 1 =3 andc 2 =1. The unique solution follows:

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

6.12. Consider the third-order homogeneous recurrence relationan= 6 an− 1 − 12 an− 2 + 8 an− 3

(a) Find the general solution.

(b) Find the solution with initial conditionsa 0 = 3 ,a 1 = 4 ,a 2 = 12.

(a) First we find the characteristic polynomial

(x)=x^3 − 6 x^2 + 12 x− 8 =(x− 2 )^3

Then
(x)has only one rootr 0 =2 which has multiplicity 3. Thus the general solution of the recurrence relation

follows:

an=c 1 ( 2 n)+c 2 n( 2 n)+c 3 n^2 ( 2 n)=(c 1 +c 2 n+c 3 n^2 )( 2 n)

(b) We find the values forc 1 ,c 2 , andc 3 as follows:

Forn= 0 ,a 0 =3 we get: c 1 = 3

Forn= 1 ,a 1 =4 we get: 2c 1 + 2 c 2 + 2 c 3 = 4

Forn= 2 ,a 2 =12 we get: 4c 1 + 8 c 2 + 16 c 3 = 12

Solving the system of three equations inc 1 ,c 2 ,c 3 yields the solution

c 1 = 3 ,c 2 =− 2 ,c 3 = 1

Thus the unique solution of the recurrence relation follows:

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