How do you get the characteristic polynomial of a recursion?

Question

For example, the characteristic polynomial of the Fibonacci sequence is $x^2 -x -1$. What are the steps involved in this?

Answer 1

If you just want the computational answer, write the recurrence in the form $c_{n+k}f_{n+k}+c_{n+k-1}f_{n+k-1}+\cdots+c_nf_n=0$. Then, the characteristic polynomial will be $c_{n+k}x^k + c_{n+k-1}x^{k-1}+\cdots + c_n=0$. The notation looks kind of messy, but examples will help. If you want an explanation of why it's called "characteristic polynomial" and how it relates to linear algebra, see e.g. here.

For fibonacci numbers, we have $F_{n+2} = F_{n+1}+F_n$, so $F_{n+2}-F_{n+1}-F_n=0$, giving us $c(x) = x^2-x-1$. If you want, you can think of it as simply replacing $F_n \to x^n$, $F_{n+1}\to x^{n+1}$, etc., and dividing by $x^n$. Notice another interesting property - the characteristic polynomial doesn't depending on the starting value $F_0$ and $F_1$. For example, if we instead define the Lucas sequence $2, 1, 3, 4, 7, 11, 18, \cdots$ with the same recurrence, we will get the same polynomial $x^2 - x - 1$.

Another example would be the recurrence $F_{n+4}=2F_{n+3}-F_n$. Then, $F_{n+4}-2F_{n+3}+5F_n=0$, giving us $x^4-2x^3+5=0$. Be careful with the missing terms (that's why I suggest using the $F_n \to x^n$ method to visualise it better).

Hope this helps!