Discrete Mathematics for Computer Science

582 CHAPTER 9 Recurrence Relations

9.12.2 Starting to Review

1. For n = 0, 1, 2, and 3, show that Yn = 2 • 3' is a solution for yo = 2 and Yn =^3 Yn-1
   for n > 0.

2. For n = 0, 1, 2, and 3, show that Yn = I/n! is a solution for yo = 1 and Yn = Yn-1/ n

for n > 0.

3. Find the value of a, for n = 0, 1, 2, 3, 4, and 5 where an = 3a,_1 - 2an-2 for n > 2
   where ao = 2 and al = -3.


4. For n = 2, 3, and 4, determine if Fn = 3 • 2n + 5 • 3n is a solution for Hn = 5Hn 1 -
   6Hn- 2 where H 0 = 8 and HI = 21.


5. Find the characteristic equation for the recurrence relation F, = Fn-1 + 3F,-2 -
   6Fn-3.


6. Let x^2 - 4x - 5 = 0 be the characteristic equation for a second-order recurrence re-
   lation F(n) for n e N. Find the general solution for this recurrence relation.


7. Let an = A2n ± BYn be the general solution of a recurrence relation with initial
   conditions ao = 0 and a, = 1. Find the particular solution that satisfies these initial
   conditions.


8. Let an = an - 1 + n where ao = 0. Solve for an.


9. Solve the Lucas recurrence relation: Ln = Ln- 1 + Ln- 2 where L 0 = 2 and L 1 = 1.
   (A definition of Lucas numbers is given in Exercise 25 found in Section 1.9.)


10. Solve a, = a,/ 2 + 1 where aI = 1 and n = 2 k for k E N.

9.12.3 Review Questions

1. Prove that the sequence bn = C where C is a constant and n E N is a solution to the
   recurrence relation an - an = 0 for n > 1 where ao = C.


2. Find the unique solution to the recurrence relation in Exercise 1 where ao = 5.


3. Prove that the sequence bn = C 1 + C 2 2n where C 1 and C 2 are constants is a solution
   to the recurrence relation an - 3an- I + 2an- 2 = 0.


4. Find the unique solution to the recurrence relation in Exercise 3 where ao = 5 and
   al =-6.


5. Conjecture and prove a formula for the sum of the elements of the Lucas sequence
   given

L0 +- L1 +L24-'"+-Ln

where n e N.

6. Find a recurrence relation for the number of ways to arrange flags on a flagpole that is
   n-feet tall using red flags two-feet high and white flags one-foot high. Suppose there
   are three times as many white flags as red flags on any flagpole. Flags of the same
   color may occur next to each other.


7. Solve a, = a, 1 + n (n - 1) for n > 1 where ao = 1.


8. Solve a, - 3a,_- - 4an-2 = 0 for n > 2 where a 0 = al = 1.


9. Verify by induction that a function of the form a, = Al n + A 2 where A 1 , A 2 E R is a
   solution to an = da,/d + e where n = dk for k e N.


10. Solve an = 7an/3 - 5 where aI = 5 and n = 3k for k c N.


11. Find a recurrence relation for the number of ways to make a pile of n chips using
    garnet, gold, red, white, and blue chips such that no two gold chips are together.