Solving Recurrences: Exercises

Use the expand-guess-verify method to find and verify a closed form solution for each sequence below.

  1. T(1) = 1 T(n) = 3 + T(n-1)

  2. S(1) = 1
    S(n) = 1 + S(n/2)

  3. T(1) = 1
    T(n) = 1 + 2*T(n/2)

  4. T(1) = 1
    T(n) = n + 2*T(n/2)

  5. M(1) = 1
    M(n) = 3*M(n-1) + 1

    Hint: 1 + 3 + 9 + ... + 3n-1 = (3n-1)/2