Solving Linear Recurrences

Solving a linear recurrence simply means trading a step-by-step rule for a formula that jumps straight to any term. "Linear" means each term is just a fixed multiple of earlier terms added together, with no squaring or multiplying terms by each other. All we're really doing is guessing that the answer is a geometric sequence and checking which ratios work. The formula line looks heavy, but there are only three pieces: the recurrence (each term is $c_1$ of the last one plus $c_2$ of the one before), the characteristic equation $x^2 = c_1x + c_2$ (an ordinary quadratic, which tells you the good ratios $x_1$ and $x_2$), and the answer $\alpha x_1^n + \beta x_2^n$ (some amount of each, with $\alpha$ and $\beta$ set by where the sequence starts). If you've solved quadratics before, you already have every tool you need.

Why guess $x^n$? Think back to the last lesson. A geometric sequence is the simplest kind of recurrence: each term is $x$ times the previous one. So it makes sense to ask whether some geometric sequence also satisfies a two-term recurrence. Substituting $a_n = x^n$ gives $x^n = c_1x^{n-1} + c_2x^{n-2}$, and dividing by $x^{n-2}$ leaves $x^2 = c_1x + c_2$. So $x^n$ works exactly when $x$ is a root of that quadratic.

One root sequence won't usually match your starting values, though, so what can we do now? Notice the recurrence is linear: if two sequences satisfy it, so does any combination $\alpha x_1^n + \beta x_2^n$, because you can add the two equations and scale them. That gives us two free constants, and the two starting values pin down $\alpha$ and $\beta$.

Example. $a_n = 5a_{n-1} - 6a_{n-2}$ with $a_0 = 1$, $a_1 = 4$. The characteristic equation $x^2 - 5x + 6 = 0$ has roots 2 and 3, so $a_n = \alpha 2^n + \beta 3^n$. From $\alpha + \beta = 1$ and $2\alpha + 3\beta = 4$, we get $\beta = 2$ and $\alpha = -1$. So $a_n = 2 \cdot 3^n - 2^n$.

Fibonacci (Binet's formula). Here $x^2 = x + 1$ has roots $\varphi = \frac{1 + \sqrt5}{2}$ and $\psi = \frac{1 - \sqrt5}{2}$, and the starting values give

It's a little amazing that all those square roots of 5 cancel to give whole numbers every time. Since $|\psi| < 1$, the $\psi^n$ part shrinks toward 0, so $F_n$ is the integer nearest $\varphi^n/\sqrt5$.

Repeated root. If $x^2 = c_1x + c_2$ has a double root $x_0$, you only get one root sequence, which isn't enough to match two starting values. The fix is to multiply by $n$: the solutions are $(\alpha + \beta n)x_0^n$. If you've seen differential equations, this is the same move as $te^{rt}$.

In the long run the root of largest absolute value dominates, because its powers outgrow the other's. That's why Fibonacci numbers grow like $\varphi^n$, and why their ratios approach $\varphi$, as we saw in the last lesson.

Engineers analyze digital filters with linear recurrences, and the same characteristic-root method solves the linear differential equations of circuits and springs.