Characteristic equation of a linear recurrence

For a constant-coefficient linear recurrence relation, substituting a trial sequence $u_n=r^n$ produces a polynomial equation in $r$ called its characteristic equation. Repeated roots contribute factors polynomial in $n$.

A nonzero root $\mu$ of multiplicity $m$ supplies $m$ independent solutions $n^j{\mu }^n$ to a constant-coefficient linear recurrence relation. Substitution $y_n={\mu }^n{z}_n$ reduces its repeated factor to the $m$th forward difference operator. A zero root needs separate initial-data treatment: for characteristic polynomial ${\lambda }^m$, the recurrence is $y_{n+m}=0$, leaving the first $m$ values arbitrary.

For a linear recurrence relation with two distinct characteristic equation of a linear recurrence roots $r_1,r_2$, the solution is $u_n=A{r}_1^n+B{r}_2^n$. If $|r_1|<1<|r_2|$, boundedness for $n\to \infty$ forces $B=0$, and $u_0$ fixes $A$. This selects the decaying discrete mode in a finite difference method for a boundary problem on an unbounded interval. Roots on the unit circle require separate treatment; a repeated root there can contribute an unbounded factor $n$.