Chapter 18 — Key Takeaways
Recurrence Relations: When the Answer Depends on Itself. A one-page reference. Reread before the exam.
Core definitions
| Term | One-line definition |
|---|---|
| Recurrence relation | An equation giving $a_n$ in terms of earlier terms $a_0,\dots,a_{n-1}$. |
| Initial condition | An explicitly given early term. A recurrence of order $k$ needs $k$ of them. |
| Order | How many terms back the recurrence reaches (deepest term with nonzero coefficient). |
| Closed form | An explicit formula for $a_n$ from $n$ alone — the goal of solving a recurrence. |
| Characteristic equation | For $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k}$: $r^k - c_1 r^{k-1} - \cdots - c_k = 0$. |
A recurrence without initial conditions does not determine a sequence. Recurrence + $k$ initial conditions = one sequence.
Classify first — it picks the method
| Question | Yes → | No → |
|---|---|---|
| Linear combo of previous terms, constant coefficients? | use characteristic equation | nonlinear / variable-coeff: outside this chapter |
| Any standalone term $f(n)$ (no $a_{n-i}$)? | nonhomogeneous (add a particular solution) | homogeneous (roots alone) |
Spot-checks: $a_n = a_{n-1}a_{n-2}$ → nonlinear. $a_n = n\,a_{n-1}$ → variable coeff (gives $n!$). $a_n = 2a_{n-1}+1$ → nonhomogeneous. "Linear" is about the $a$'s, not the growth rate ($a_n = 2a_{n-1}$ is linear but grows like $2^n$).
The characteristic-equation method (linear, homogeneous, constant coeffs)
| Step | Do this |
|---|---|
| 1 | Form characteristic eq.: replace $a_{n-i}$ with $r^{k-i}$. |
| 2 | Find roots + multiplicities. |
| 3 | Each root $r$ of multiplicity $m$ → basic solutions $r^n, nr^n, \dots, n^{m-1}r^n$. |
| 4 | General solution = linear combination of all basic solutions. |
| 5 | Solve for the constants using the $k$ initial conditions (last). |
Second-order cheat sheet — $a_n = c_1 a_{n-1} + c_2 a_{n-2}$, char. eq. $r^2 - c_1 r - c_2 = 0$
| Roots | General solution |
|---|---|
| Distinct $r_1 \ne r_2$ | $a_n = \alpha\, r_1^{\,n} + \beta\, r_2^{\,n}$ |
| Repeated $r_0$ | $a_n = (\alpha + \beta n)\, r_0^{\,n}$ |
Discriminant $c_1^2 + 4c_2$: $>0$ distinct real, $=0$ repeated, $<0$ complex (still works, complex roots).
Nonhomogeneous: $a_n = (\text{linear part}) + f(n)$
$$\boxed{a_n = a_n^{(h)} + a_n^{(p)}}$$ $a_n^{(h)}$ = general solution of the associated homogeneous recurrence (drop $f(n)$); $a_n^{(p)}$ = any one particular solution. Fit constants to initial conditions after adding $a_n^{(p)}$.
| Forcing $f(n)$ | Trial $a_n^{(p)}$ |
|---|---|
| constant $C$ | constant $A$ |
| degree-$d$ polynomial | general degree-$d$ polynomial |
| $C s^n$, $s$ not a char. root | $A s^n$ |
| trial clashes with a homogeneous solution | multiply trial by $n$ (then $n^2$, …) |
Results you should recognize on sight
| Problem | Recurrence | Closed form |
|---|---|---|
| Tower of Hanoi (min moves) | $H_n = 2H_{n-1}+1,\ H_0=0$ | $H_n = 2^n - 1$ |
| $2\times n$ domino tilings | $t_n = t_{n-1}+t_{n-2}$ | $t_n = F_{n+1}$ |
| Binary strings with no "00" | $s_n = s_{n-1}+s_{n-2}$ | $s_n = F_{n+2}$ |
| Fibonacci | $F_n = F_{n-1}+F_{n-2}$ | $\frac{1}{\sqrt5}(\phi^n - \psi^n)$ — Ch. 19 |
Two universal setup moves: peel off the structure (biggest/last piece) or condition on the last choice (how does it end?).
Code → recurrence (the analysis reflex)
| Code shape | Time recurrence | Growth |
|---|---|---|
| one call on $n-1$, $O(1)$ work | $T(n)=T(n-1)+c$ | $O(n)$ |
| one call on $n-1$, $O(n)$ work | $T(n)=T(n-1)+cn$ | $O(n^2)$ |
| one call on $n/2$, $O(1)$ work | $T(n)=T(n/2)+c$ | $O(\log n)$ (Ch. 19) |
| two calls on $\approx n$ | $T(n)=T(n-1)+T(n-2)+c$ | exponential ($\approx \phi^n$) |
Recipe: (1) how does the input shrink and into how many pieces? → terms on the right. (2) work done outside the recursive calls? → the $f(n)$.
Common pitfalls
- Too few initial conditions. Order-$k$ needs $k$; Fibonacci needs two.
- Confusing "linear" with "linear growth." A linear recurrence can grow exponentially.
- Fitting constants too early. For nonhomogeneous, add $a_n^{(p)}$ first, then use the initial conditions on the full $a_n^{(h)} + a_n^{(p)}$.
- Forgetting the repeated-root factor of $n$. $(r-r_0)^2$ gives $r_0^n$ and $nr_0^n$ — not two copies of $r_0^n$.
- Particular-solution clash. If the trial is already a homogeneous solution, multiply by $n$.
Toolkit addition (recurrences.py)
solve_linear(coeffs, inits, n)
# coeffs=[c1,...,ck] (c1 * a_{n-1}); inits=[a0,...,a_{k-1}]; returns a_n. O(n*k), unrolls.
solve_linear([1, 1], [0, 1], 10) # -> 55 (Fibonacci F_10)
solve_linear([5, -6], [1, 4], 5) # -> 454
Joins check_identity/fib (Ch. 6). Chapter 19 adds the $O(\log n)$ matrix fib.
Bridge to Chapter 19
Characteristic equations don't solve divide-and-conquer recurrences $T(n)=aT(n/b)+f(n)$ — those need the recursion-tree method and the Master Theorem (merge sort $O(n\log n)$, binary search $O(\log n)$). And $r^2-r-1=0$ unlocks Fibonacci's golden-ratio closed form + $O(\log n)$ matrix exponentiation.