Solving Recurrences: Exercises
Use the expand-guess-verify method to find and verify a closed form solution for each sequence below.
T(1) = 1 T(n) = 3 + T(n-1)
S(1) = 1
S(n) = 1 + S(n/2)
T(1) = 1
T(n) = 1 + 2*T(n/2)
T(1) = 1
T(n) = n + 2*T(n/2)
M(1) = 1
M(n) = 3*M(n-1) + 1
Hint: 1 + 3 + 9 + ... + 3
^{n-1}
= (3
^{n}
-1)/2