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

122 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6

6.33. Find the unique solution to each recurrence relation with the given initial conditions:

(a)an= 10 an− 1 − 32 an− 2 + 32 an− 3 witha 0 = 5 ,a 1 = 18 ,a 2 = 76

(b)an= 9 an− 1 − 27 an− 2 + 27 an− 3 witha 0 = 5 ,a 1 = 24 ,a 2 = 117

6.34. Consider the following second-order recurrence relation and its characteristic polynomial
(x):

an=san− 1 +tan− 2 and 
(x)=x^2 −sx−t(∗)

(a) Supposep(n) andq(n) are solutions of (∗). Show that, for any constantsc 1 andc 2 ,c 1 p(n)+c 2 q(n)is also a solution

of (∗).

(b) Supposeris a root of
(x). Show thatan=rnis a solution to (∗).

(c) Supposeris a double root of
(x). Show that: (i)s= 2 randt=−r^2 ; (ii)an=nrnis also a root of (∗).

6.35. Repeat Problem 6.34(a) and (b) for any linearkth-order homogeneous recurrence relation with constant coefficients
and its characteristic polynomial
(x)which have the form:

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

∑k

i= 1

C 1 an− 1 and 
(x)=xk−

∑k

i= 1

C 1 xk−i

Answers to Supplementary Problems

6.13. (a) 286; (b) 646.

6.14. 78.

6.15. 15.

6.16. 520.

6.17. ( 14 !)/[( 3! 3! 2! 2! 2! 2 !)( 2! 4 !)]=3 153 150.

6.18. (a) (i) 3^3 =27; (ii) They may be distributed as: [3, 0,
0], [2, 1, 0], or [1, 1, 1]. Hencem= 1 + 3 + 1 =5.
(b) (i) 3^4 =81; (ii) They may be distributed as: [4, 0,
0], [3, 1, 0], [2, 2, 0] or [2, 1, 1]. Hencem= 1 + 4 + 3 +
6 =14.

6.19. (a) 5796; (b) 1560; (c) 5!=120; (d) 0.

6.20. (a)(Dm)^2 ; (b)(m!)^2.

6.21. 701.

6.22. There are eight triplets of parities: (odd, odd, odd),
(odd, odd, even),.... Thus 2 of the 9 points have the
same triplet of parities.

6.23. 2, 3, 10, 20; 25, 15, 10, 8, 4.

6.24. Use Theorem 6.7 withn=9.

6.25. 5, 4, 3, 2, 1, 10, 9, 8, 7, 6,..., 25, 24, 23, 22, 21.

6.26. (Hint: See Problem 6.9.)

6.27. (Hint: PartitionTinto 9 equilateral triangles where each
side has length one inch.)

6.28. Letsi=x 1 +···+xi. The result is true ifndivides

somesi. Otherwise, letr′be the remainder whensiis

divided byn. Two of the rs must be equal. Sayrp=rq

wherep<q. Thenndividessq−sp=xp+ 1 +···+xq.

6.31. (a)an=c 1 ( 5 n)+c 2 (− 2 )n; c 1 = 3 ,c 2 = 2

(b)an=c 1 ( 7 n)+c 2 (− 3 )n; c 1 = 4 ,c 2 = 5

(c)an=c 1 +c 2 ( 2 n); c 1 = 2 ,c 2 = 3

(d)an=c 1 ( 2 n)+c 2 ( 3 n); c 1 =− 2 ,c 2 = 4

(e)an=c 1 [( 3 +t)/ 2 ]n+c 2 [( 3 −t)/ 2 ]n; c 1 = 1 /t,

c 2 =− 1 /twheret=

√

5

(f)an=c 1 [( 5 +s)/ 2 ]n+c 2 [( 5 −s)/ 2 ]n; c 1 = 1 /s,

c 2 =− 1 /swhere=

√

13

6.32. (a)an=c 1 ( 6 n), c 1 = 5

(b)an=c 1 ( 7 n), c 1 = 5

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

(d)an=c 1 ( 5 n)+c 2 n( 5 n), c 1 = 2 ,c 2 = 1

6.33. (a)an= 2 ( 4 n)+n( 4 n)+ 3 ( 2 n);(b)an= 5 ( 3 n)+

2 n( 3 n)+n^2 ( 3 n)=( 5 + 2 n+n^2 ) 3 n.

6.34. (b)ris a root of
(x)sor^2 −sr−t=0orr^2 =sr+t.

Letan=rn. Thensan− 1 +tan− 2 =srn−^1 +trn−^2 =

(sr+t)rn−^2 =r^2 (rn−^2 )=rn=an

(c) (i)ris a double root of
(x); hence
(x) =

(x−r)^2 =x^2 − 2 rx+r^2 =x^2 −sx−t. Thuss= 2 r

andt=−r^2. (ii) Letannrn. Thensan− 1 +tan− 2 =

nrn=an.