CSC 133 Discrete Structures Quiz

1. Given the recurrence ak = -ak - 1 + 12ak - 2, a0 = 1, a1 = 8.

  1. Write out the next three terms of this sequence.
    4, 92, -44
  2. What is the characteristic equation?
    t2 + t - 12 = 0
  3. Given the roots to the characteristic equation are r = 3 and s = -4, write an equation for an based on the linear combination of the roots to this characteristic equation using real constants C and D.
    an = C(3)n + D (-4)n.
  4. Use the initial conditions to solve for the constants C and D and write an explicit formula for the recurrence relation.
    a0 = C(3)0 + D (-4)0 = 1 ® C = 1 - D, a1 = (1 - D )(3)1 + D (-4)1 = 8 ® D = (8 - 3)/(-4 - 3) = 5/(-7) = -.714285714286,
    C = 1 - D = 1 + 5/7 = 12/7 = 1.71428571429.
    an = (12/7)(3)n - (5/7)(-4)n.
  5. Show that your formula works for a2.
    a2 = (12/7)(3)2 - (5/7)(-4)2 = 4.

2. Given the recurrence ak = 10ak - 1 - 25ak - 2, a0 = 0, a1 = 1.

  1. Write out the next three terms of this sequence.
    10, 75, 500
  2. What is the characteristic equation?
    t2 - 10t + 25 = 0
  3. Given the roots to the characteristic equation both t = 5, write an equation for an based on the linear combination of the roots to this characteristic equation using real constants C and D.
    an = C× 5n + D× n× 5n.
  4. Use the initial conditions to solve for the constants C and D and write an explicit formula for the recurrence relation.
    a0 = C(5)0 + D(0)(5)0 = 0 ® C = 0, a1 = 0(5)1 + D(1)(5)1 = 1 ® D = 1/5.
    an = (1/5)(n)(5)n = n    × 5n - 1.
  5. Show that your formula works for a2.
    a2 = 2× 52 - 1 = 2× 5 = 10.