Characteristic polynomials

The characteristic polynomial of a linear recurrence

$$c_k a_{n+k} + c_{k-1} a_{n+k-1} + \cdots + c_1 a_{n+1} + c_0 a_n = 0$$

is defined to be the polynomial

$$c_k x^k + c_{k-1} x^{k-1} + \cdots + c_1 x + c_0.$$

For example, the characteristic polynomial of the recurrence $a_{n+1}-2a_n=0$ satisfied by the sequence (1) is $x-2$.

Here is another example: the famous Fibonacci sequence

$$\{F_n\}_{n=0}^\infty = 0, 1, 1, 2, 3, 5, 8, 13, \dots$$

which can be described by the starting values $F_0=0$, $F_1=1$ and the recurrence relation

$$F_n=F_{n-1}+F_{n-2} n \ge 2$$ (3)

To find the characteristic polynomial, we first need to rewrite the recurrence relation in the form (2). The relation (3) is equivalent to

$$F_{n+2}=F_{n+1}+F_n n \ge 0$$ (4)

Rewriting it as

$$F_{n+2}-F_{n+1}-F_n=0$$ (5)

shows that $\{F_n\}$ is a linear recursive sequence satisfying a recurrence of order 2, with $c_2=1$, $c_1=-1$, and $c_0=-1$. The characteristic polynomial is $x^2-x-1$.