Unrolling works when each term depends on one earlier term. Recurrences like $a_{n} = a_{n-1} + a_{n-2}$ reach back two steps, and unrolling gets messy. Instead we guess the shape of the answer, and the guess reduces to a quadratic equation, solved with the quadratic formula or by factoring. It is the systematic follow-up to unrolling.
Key idea
For $a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2}$, solve the characteristic equation $r^{2} = c_{1}r + c_{2}$. If its roots $r_{1} \ne r_{2}$, every solution is $a_{n} = A\,r_{1}^{n} + B\,r_{2}^{n}$; find $A$ and $B$ from the two starting values.
Why it works
Try $a_{n} = r^{n}$. Substituting gives $r^{n} = c_{1}r^{n-1} + c_{2}r^{n-2}$; dividing by $r^{n-2}$ leaves $r^{2} = c_{1}r + c_{2}$. So $r^{n}$ is a solution exactly when $r$ is a root. The recurrence is linear, so any combination $Ar_{1}^{n} + Br_{2}^{n}$ of two solutions is again a solution. Two free constants can match any two starting values (the equations $A + B = a_{0}$, $Ar_{1} + Br_{2} = a_{1}$ have a solution when $r_{1} \ne r_{2}$), and two starting values determine the whole sequence.
Worked examples
Worked example: Two whole-number roots
Solve $a_{n} = 5a_{n-1} - 6a_{n-2}$ with $a_{0} = 1$, $a_{1} = 4$.
- Characteristic equation: $r^{2} = 5r - 6$, so $r^{2} - 5r + 6 = 0 = (r - 2)(r - 3)$: roots $2$ and $3$.
- $a_{n} = A \cdot 2^{n} + B \cdot 3^{n}$. From $n = 0$: $A + B = 1$. From $n = 1$: $2A + 3B = 4$.
- Subtract twice the first equation from the second: $B = 2$, so $A = -1$.
- $a_{n} = 2 \cdot 3^{n} - 2^{n}$. Check $a_{2}$: the formula gives $18 - 4 = 14$; the recurrence gives $5 \cdot 4 - 6 \cdot 1 = 14$.
Answer: $a_{n} = 2 \cdot 3^{n} - 2^{n}$
Worked example: A negative root
Solve $a_{n} = a_{n-1} + 2a_{n-2}$ with $a_{0} = 2$, $a_{1} = 1$.
- $r^{2} = r + 2$, so $r^{2} - r - 2 = (r - 2)(r + 1) = 0$: roots $2$ and $-1$.
- $A + B = 2$ and $2A - B = 1$. Adding: $3A = 3$, so $A = 1$ and $B = 1$.
- $a_{n} = 2^{n} + (-1)^{n}$: $2, 1, 5, 7, 17, \ldots$, which matches the recurrence.
Answer: $a_{n} = 2^{n} + (-1)^{n}$
Worked example: The Fibonacci numbers
What does this method give for $F_{n} = F_{n-1} + F_{n-2}$, $F_{0} = 0$, $F_{1} = 1$?
- $r^{2} = r + 1$ has roots $\varphi = \frac{1 + \sqrt{5}}{2}$ and $\psi = \frac{1 - \sqrt{5}}{2}$.
- Fitting $A + B = 0$ and $A\varphi + B\psi = 1$ gives $A = \frac{1}{\sqrt{5}}$, $B = -\frac{1}{\sqrt{5}}$.
- So $F_{n} = \dfrac{\varphi^{n} - \psi^{n}}{\sqrt{5}}$ (Binet's formula). Since $|\psi| < 1$, $F_{n}$ is the whole number nearest $\varphi^{n}/\sqrt{5}$.
Answer: $F_{n} = \dfrac{\varphi^{n} - \psi^{n}}{\sqrt{5}}$
Common mistake
Wrong signs in the characteristic equation, or fitting only one starting value. For $a_{n} = 5a_{n-1} - 6a_{n-2}$ the equation is $r^{2} - 5r + 6 = 0$, not $r^{2} + 5r - 6 = 0$: move the terms across the equals sign and their signs change. And $A$ and $B$ need both $a_{0}$ and $a_{1}$; a formula fitted to $a_{0}$ alone is just a guess. Check: compute $a_{2}$ from your formula and from the recurrence.