= Characteristic polynomial of a linear recurrence
{title2=$p(t)=t^r-c_{r-1}t^{r-1}-\cdots-c_0$}
For the constant-coefficient homogeneous <linear recurrence relation> $u_{n+r}=\sum_{j=0}^{r-1}c_ju_{n+j}$, its <characteristic polynomial> is
$$
p(t)=t^r-\sum_{j=0}^{r-1}c_jt^j.
$$
A nonzero root $\lambda$ gives the solution $u_n=\lambda^n$. Over a <field> of <characteristic> zero, a root of multiplicity $m$ contributes $\lambda^n,n\lambda^n,\ldots,n^{m-1}\lambda^n$ when $\lambda\ne0$. The <Fibonacci sequence> has $p(t)=t^2-t-1$, whose roots give its familiar closed formula.
Equivalently, $p$ annihilates the shift on every solution. Reducing $t^N$ modulo $p(t)$ therefore expresses the distant term $u_N$ as a <linear combination> of $u_0,\ldots,u_{r-1}$. Repeated squaring in the <polynomial quotient ring> gives this combination using logarithmically many multiplications in $N$.
Back to article page
