Which recurrence-solving method do I need?
The decision path from a new recurrence to first-order, characteristic-root, or generating-function methods.
Reach for this whenever a recurrence needs a closed form and it is not obvious which chapter's method applies. Check the recurrence's order and homogeneity first, then whether its characteristic roots repeat, before reaching for a generating function as a last resort.
Step 1 — is it first-order?
Needed once the recurrence has order 2 or higher.
Step 2 — does the characteristic equation have a repeated root?
A double root needs an extra factor of n in the solution, not just r^n.
Step 3 — is a closed form resisting both methods above?
Bookkeeping device that can solve recurrences a characteristic equation struggles with.
For divide-and-conquer recurrences specifically, skip straight to this instead.
Formulas this decision path leads to
If a_n = c\,a_{n-1} + d for n \ge 1 with constants c \neq 1 and d, then for every n \ge 0, a_n = c^n a_0 + d\,\frac{c^n - 1}{c - 1}.
Show proof
Unroll the recurrence one step at a time. Substituting the recurrence into itself, a_n = c\,a_{n-1} + d = c(c\,a_{n-2} + d) + d = c^2 a_{n-2} + cd + d, and after k substitutions a_n = c^k a_{n-k} + d\left(c^{k-1} + c^{k-2} + \cdots + c + 1\right). (Formally this is an induction on k: the case k=1 is the recurrence itself, and applying the recurrence to a_{n-k} extends the pattern from k to k+1.) Taking k = n reaches the initial term: a_n = c^n a_0 + d\sum_{i=0}^{n-1} c^i. Since c \neq 1, the finite geometric sum evaluates to \sum_{i=0}^{n-1} c^i = \frac{c^n - 1}{c - 1}, giving a_n = c^n a_0 + d\,\frac{c^n - 1}{c - 1}. When n = 0 both sides equal a_0, so the formula holds for all n \ge 0.
For the Fibonacci sequence defined by F_0=0, F_1=1, and F_n = F_{n-1}+F_{n-2} for n\ge 2, the ordinary generating function is F(x) = \sum_{n\ge 0} F_n x^n = \frac{x}{1-x-x^2}.
Show proof
Let F(x)=\sum_{n\ge 0}F_n x^n. Multiply the recurrence F_n = F_{n-1}+F_{n-2} by x^n and sum over every n\ge 2 where it holds: \sum_{n\ge 2} F_n x^n \;=\; \sum_{n\ge 2} F_{n-1}x^n \;+\; \sum_{n\ge 2} F_{n-2}x^n. Each sum is a piece of F(x). The left side is F(x) minus its first two terms: F(x) - F_0 - F_1 x = F(x) - x. Re-indexing the first sum on the right with m = n-1 gives \sum_{m\ge 1} F_m x^{m+1} = x\bigl(F(x)-F_0\bigr) = xF(x), and re-indexing the second with m=n-2 gives \sum_{m\ge 0} F_m x^{m+2} = x^2 F(x). So F(x) - x = xF(x) + x^2F(x). Collecting every F(x) term on the left, F(x)\left(1 - x - x^2\right) = x, and dividing by the formal power series 1-x-x^2 (invertible since its constant term is nonzero) gives F(x) = \frac{x}{1-x-x^2}. Factoring 1-x-x^2 = (1-\varphi x)(1-\psi x) with \varphi = \frac{1+\sqrt5}{2} and \psi = \frac{1-\sqrt5}{2}, partial fractions split F(x) into two geometric series and reading off the coefficient of x^n recovers Binet's formula F_n = \frac{\varphi^n - \psi^n}{\sqrt5}.