Recurrence Relations and Characteristic Roots · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

From a recurrence to a closed formula

Mathematics · Discrete Mathematics · ages 19-20
Name ______________________   Date ____________

  1. A sequence starts a0 = 1, a1 = 1, with each later term the sum of the two before it. What is a5? Give a number.

    Answer: ______________

  2. A sequence starts a0 = 1, a1 = 1, with each later term the sum of the two before it. What is a5? Give a number.

    Answer: ______________

  3. For the recurrence a(n) = 5 times a(n minus 1) minus 6 times a(n minus 2), which numbers are the characteristic roots?

    • 1 and 6
    • -2 and -3
    • 2 and 3

  4. A rabbit colony starts with 3 pairs and doubles every month. How many pairs are there after 4 months?

    • 48
    • 24
    • 96

  5. A sequence obeys a(n) = 2 times a(n minus 1) plus 1 with a0 = 4. Its closed form is a(n) = 5 times 2 to the power n minus 1. What is a2? Give a number.

    Answer: ______________

  6. Lee says that for a repeated root r = 2, A times 2 to the power n plus B times 2 to the power n already covers all solutions. Is Lee right?

    Circle one:   True   False

  7. A sequence obeys a(n) = 2 times a(n minus 1) plus 1 with a0 = 4. Its closed form is a(n) = 5 times 2 to the power n minus 1. What is a2? Give a number.

    Answer: ______________

  8. For the recurrence a(n) = 5 times a(n minus 1) minus 6 times a(n minus 2), which numbers are the characteristic roots?

    • 2 and 3
    • 1 and 6
    • -2 and -3
    • 2 and -3

  9. You found roots 2 and 3, so the solution looks like A times 2 to the power n plus B times 3 to the power n. How do you fit A and B?

    • Use the starting values as simultaneous equations for A and B
    • Guess new roots from the starting values
    • Divide the roots by the starting values

  10. The characteristic equation r squared minus 4 r plus 4 = 0 has the repeated root r = 2. What is the general form of the solution?

    • A times 2 to the power n plus B times n times 2 to the power n
    • A times 2 to the power n plus B times 4 to the power n
    • A times 2 to the power n plus B times 3 to the power n
    • A times n plus B times 2 to the power n
LightMySky · lightmysky.comW1-mt_q0b2bi0iAB-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

From a recurrence to a closed formula W1-mt_q0b2bi0iAB-s1

  1. 8 · Each term is the sum of the two before: 1, 1, 2, 3, 5, 8, so the 5th term after a0 is 8.
  2. 8 · Each term is the sum of the two before: 1, 1, 2, 3, 5, 8.
  3. 2 and 3 · Trying r to the power n gives r squared minus 5 r plus 6, which factors into (r minus 2)(r minus 3).
  4. 48 · Doubling each month from 3 pairs gives 6, 12, 24, then 48 pairs.
  5. 19 · The closed form 5 times 2 to the power n minus 1 fits a0 = 4, and at n = 2 it gives 20 minus 1 = 19.
  6. False · Lee is wrong. Both terms collapse into one constant, and the n factor is what makes the second solution independent.
  7. 19 · The closed form 5 times 2 to the power n minus 1 fits a0 = 4, and at n = 2 it gives 20 minus 1.
  8. 2 and 3 · Trying r to the power n gives r squared minus 5 r plus 6 = 0, which factors as (r minus 2)(r minus 3) = 0.
  9. Use the starting values as simultaneous equations for A and B · Each starting value gives one equation, and the two equations pin down the two constants.
  10. A times 2 to the power n plus B times n times 2 to the power n · A repeated root r = 2 supplies one solution 2 to the power n, and the extra factor of n supplies the second independent one.
Worksheet · LightMySky