# 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\)