 Characteristic polynomial of a linear recurrence

For the constant-coefficient homogeneous linear recurrence relation $u_{n+r}={\sum }_{j=0}^{r-1}{c}_j{u}_{n+j}$, its characteristic polynomial isA 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,\dots ,n^{m-1}{\lambda }^n$ when $\lambda \ne 0$. 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,\dots ,u_{r-1}$. Repeated squaring in the polynomial quotient ring gives this combination using logarithmically many multiplications in $N$.