Recurrence Relations

Characteristic equation, roots, and the closed-form solution.

The idea

A recurrence relation defines a sequence by a rule that produces each term from earlier ones, together with enough initial values to start the rule. A closed form instead states $a_n$ directly as a formula in $n$. The recurrence is usually easier to write down, because it describes a step-by-step process the way the process itself runs, and harder to use: computing $a_{1000}$ from the rule means computing the thousand terms before it.

Solving a recurrence means finding a closed form. For a linear recurrence with constant coefficients, $a_n = c_1 a_{n-1} + c_2 a_{n-2},$ substitute the trial solution $a_n = x^{n}$ and divide by $x^{n-2}$. The recurrence collapses to the characteristic equation $x^{2} = c_1 x + c_2.$ Each root $r$ makes $r^{n}$ a solution, and sums and constant multiples of solutions are again solutions, so distinct roots $r$ and $s$ give the general solution $a_n = A\,r^{n} + B\,s^{n}.$ The initial values then determine $A$ and $B$.

Ways to work on it

• Walkthrough. Terms, the characteristic equation, and the solution form.
• Practice. Compute a term of a recurrence.
• Hardest. Solve for the closed form and evaluate at a large index.

Not sure where to start? Take the ten-question placement test.