CSC 133 Discrete Structures Quiz (practice key)
(Calculator is highly recommended for the actual quiz.)

1. Given the recurrence ak = 3ak – 1 – 2.25ak – 2, a0 = 0, a1 = 2.

  1. Write out the first four terms of this sequence.
    0, 2, 6, 13.5
  2. What is the characteristic equation?
    t2 – 3t + 2.25 = 0, or t2 – 3t + 9/4 = 0
  3. Given the roots to the characteristic equation are both t = 1.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(1.5)n + D(n)(1.5)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(1.5)0 + D(0)(1.5)0 = 0 ® C = 0, a1 = 0(1.5)1 + D(1)(1.5)1 = 2 ® D = 4/3.
    an = (4/3)(n)(1.5)n.
  5. Show that your formula works for a2.
    a2 = (4/3)(2)(1.5)2 = 4/3× 2× 9/4 = 2× 3 =6.

2. Given the recurrence ak = 7ak – 1 – 10ak – 2, a0 = 2, a1 = 2.

  1. Write out the first four terms of this sequence.
    2, 2, -6, -62
  2. What is the characteristic equation?
    t2 – 7t + 10 = 0
  3. Given the roots to the characteristic equation are t = 2, 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× 2n + D× 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 + D = 2, C = 2 – D, a1 = C× 2 + D× 5 = 2, substituting C = 2 – D ® (2 – D)2 + D× 5 = 2, 4 – 2D + 5D = 2,
    D = -2/3, so C = 8/3.
    an = (8/3)2n – (2/3)5n.
  5. Show that your formula works for a2.
    a2 = (8/3)22 – (2/3)52 = -6.