Solving Linear Recurrences With Characteristic Roots

An interviewer gives you a recurrence like $a_n = 5a_{n-1} - 6a_{n-2}$ with $a_0 = 1$, $a_1 = 4$, and asks for $a_{20}$. You could compute nineteen steps by hand, but there's a faster route: find a formula for $a_n$ directly, plug in $n=20$, and you're done. That formula-finding trick is the characteristic-root method, and it turns almost any interview recurrence into a two-line algebra problem.

The idea: guess a geometric form

A linear recurrence says each term is a fixed linear combination of the previous few terms, like $a_n = c_1 a_{n-1} + c_2 a_{n-2}$. The trick is to guess that the solution looks like a geometric sequence, $a_n = r^n$ for some constant $r$, and see what $r$ has to satisfy. Substituting $a_n = r^n$ into $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ and dividing through by $r^{n-2}$ gives the characteristic equation:

$$r^2 - c_1 r - c_2 = 0 .$$

In plain English: this is an ordinary quadratic whose roots are exactly the values of $r$ for which $r^n$ satisfies the recurrence on its own. If the quadratic has two distinct roots $r_1$ and $r_2$, the general solution is a mix of both geometric sequences, $a_n = A \, r_1^n + B \, r_2^n$, and the two unknown weights $A$ and $B$ are pinned down by the two starting values you were given.

Worked example: the recurrence above

For $a_n = 5a_{n-1} - 6a_{n-2}$, the characteristic equation is $r^2 - 5r + 6 = 0$, which factors as $(r-2)(r-3) = 0$, giving roots $r_1 = 2$, $r_2 = 3$. So the general solution is

$$a_n = A \cdot 2^n + B \cdot 3^n .$$

Use the starting values to solve for $A$ and $B$. At $n=0$: $A + B = 1$. At $n=1$: $2A + 3B = 4$. Substituting $A = 1 - B$ into the second equation gives $2(1-B) + 3B = 4$, so $2 + B = 4$, meaning $B = 2$ and $A = -1$. The closed form is $a_n = -2^n + 2 \cdot 3^n$. Check it: $a_0 = -1 + 2 = 1$ ✓, $a_1 = -2 + 6 = 4$ ✓. Now $a_{20} = -2^{20} + 2 \cdot 3^{20}$ is a one-line calculation instead of twenty steps of substitution.

Repeated roots

If the quadratic has a repeated root $r$ (discriminant zero), the second independent solution isn't $r^n$ again — it's $n \cdot r^n$. The general solution becomes $a_n = (A + Bn) r^n$. This matters because a naive guess of $a_n = A r^n + B r^n$ collapses to a single unknown and can't match two independent starting values.

What this means in practice

Beyond puzzle recurrences, this is the exact machinery behind analyzing algorithm running times (a recurrence like $T(n) = T(n-1) + T(n-2)$ describes naive Fibonacci recursion) and behind discrete-time models of compounding processes with memory, like a portfolio rule that blends this period's and last period's signal. Whenever you see "each term depends linearly on the last one or two terms," reach for the characteristic equation instead of grinding through the recursion by hand.