Solving recurrence relations
Gain intuition and guess closed form solution
- Compute value of function at a few points
- Unfold recurrence a few steps
Testing the hypothesis
- Try to prove by induction
- Use failed attempt to refine solution
Example
$$\begin{split} T(n) &= 2T(n - 1) + 1 \end{split}$$
Compute value of function at a few points
Want to solve recurrence:
$$\begin{split} T(0) &= 0 \\ T(n) &= 2T(n - 1) + 1 \end{split}$$
Compute a few steps:
$$\begin{split} T(0) &= 0 \\ T(1) &= 2(T(0)) + 1 = 1 \\ T(2) &= 2(T(1)) + 1 = 3 \\ T(3) &= 2(T(2)) + 1 = 7 \\ T(4) &= 2(T(3)) + 1 = 15 \\ ... \end{split}$$
Hypothesis:
$$ T(n) = 2^n - 1 $$
Inductive proof:
Prove base case is true.
Show that if previous case is true: $T(n-1) = 2^(n - 1) - 1, current case \(T(n) = 2^n - 1\).
$$\begin{split} T(0) &= 0 = 2^0 - 1 \\ T(n) &= 2T(n - 1) + 1 \\ &= 2(2^{n-1} - 1) + 1 \\ &= 2^n - 1 \end{split}$$
Unroll recurrence
$$\begin{split} T(n) &= 2T(n − 1) + 1 \\ &= 2(2T(n − 2) + 1) + 1 = 4T(n − 2) + 3 \\ &= 4(2T(n − 3) + 1) + 3 = 8T(n − 3) + 7 \\ &= 16T(n − 4) + 15 \end{split}$$
Guess: \(T(n) = 2^k T(n − k) + 2^k − 1 for 1 ≤ k ≤ n\)
