Recurrences & Characteristic Equations

Study Sheet

Recurrences & Characteristic Equations

Closed forms for linear recursions

The Characteristic Equation Method

Tip
Distinct roots

For an+2=p an+1+q ana_{n+2}=p\,a_{n+1}+q\,a_n, solve x2=px+qx^2=px+q. With distinct roots r,sr,s: an=Arn+Bsna_n = A r^n + B s^n, where A,BA,B come from the first two terms.

In plain terms. Guess an=xna_n = x^n, and the recurrence becomes a quadratic in xx. Every solution is a mix of the two root-powers; the starting values fix the mix.

Example. an+2=an+1+2ana_{n+2}=a_{n+1}+2a_n has roots 2,−12,-1; with a1=1,a2=2a_1=1,a_2=2 the mix is an=2n−1a_n=2^{n-1} exactly.

Tip
Repeated roots

If the characteristic equation has a double root rr, the general solution gains a factor of nn: an=(A+Bn) rna_n = (A + Bn)\,r^n.

In plain terms. One root cannot carry two initial conditions alone — the extra nn in front supplies the second degree of freedom.

Example. an=6an−1−9an−2a_n = 6a_{n-1} - 9a_{n-2} has (x−3)2(x-3)^2: with a1=3,a2=18a_1=3, a_2=18, an=n⋅3na_n = n\cdot 3^n.

Concept
Fibonacci and Binet

Fibonacci is the recurrence x2=x+1x^2 = x+1 with roots φ=1+52\varphi = \tfrac{1+\sqrt5}{2} and φ^=1−52\hat\varphi = \tfrac{1-\sqrt5}{2}: Fn=φn−φ^n5F_n = \dfrac{\varphi^n - \hat\varphi^n}{\sqrt5}.

In plain terms. The golden ratio IS the characteristic root of Fibonacci. Since ∣φ^∣<1|\hat\varphi|<1, FnF_n is the nearest integer to φn/5\varphi^n/\sqrt5 — closed forms tame huge indices instantly.

Example. Sums telescope too: F1+F2+⋯+Fn=Fn+2−1F_1+F_2+\cdots+F_n = F_{n+2}-1, so the first ten sum to 144−1=143144-1=143.