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 relation 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.
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 relation 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.