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 bit is 0 or 1. Let b(n) count strings of n bits with no adjacent 1s. Use b0=1, b1=2 and the split by the final bit to find b6. 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. For n>=2, a(n)=a(n-1)+2*a(n-2), with a0=4 and a1=5. The roots are 2 and -1. Fit a(n)=A*2^n+B*(-1)^n, then find a3. 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 n>=2, a(n)=3*a(n-1)+4*a(n-2). Which characteristic equation follows from trying a(n)=r^n?

    • r^2+3*r+4=0
    • r^2-3*r+4=0
    • r^2-3*r-4=0
    • r^2+3*r-4=0

  9. For n>=2, a(n)=7*a(n-1)-12*a(n-2), with a0=5 and a1=17. Its characteristic roots are 3 and 4. Which closed formula fits both initial values?

    • a(n)=3*3^n+2*4^n
    • a(n)=2*3^n+3*4^n
    • a(n)=4*3^n+1*4^n

  10. For n>=2, a(n)=6*a(n-1)-9*a(n-2), with a0=2 and a1=9. The root 3 is repeated. Which formula fits both initial values?

    • a(n)=(2+1*n)*3^n
    • a(n)=(2+3*n)*3^n
    • a(n)=(3+2*n)*3^n
    • a(n)=(2-1*n)*3^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. 21 · The ending cases give b(n)=b(n-1)+b(n-2). From 1 and 2, the next counts are 3, 5, 8, 13 and 21.
  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. 23 · A+B=4 and 2A-B=5 give A=3 and B=1. Then a3=3*8-1=23.
  6. False · Lee's two terms combine into (A+B)*2^n, leaving only one free constant. The independent solution n*2^n is also needed to cover arbitrary pairs of initial values.
  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. r^2-3*r-4=0 · Substitution gives r^2=3*r+4 after division by r^(n-2). Move both right-hand terms left to get r^2-3*r-4=0.
  9. a(n)=3*3^n+2*4^n · A+B=5 and 3A+4B=17 give B=2 and A=3. Thus a(n)=3*3^n+2*4^n.
  10. a(n)=(2+1*n)*3^n · Use (A+B*n)*3^n. The initial values give A=2 and 3(A+B)=9, so B=1.
Worksheet · LightMySky