Characteristic polynomial of linear recurrences

Question

I am learning about solving linear recurrences and I am trying to understand the proof behind the solution. For example, if I have $(a_n)_{n\ge1} \subseteq \mathbb{R}$, $a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d}$
Why the characteristic polynomial of this equation is $\lambda^d - c_1 \lambda^{d-1} - c_2 \lambda^{d-2} - \cdots - c_d \lambda^0 =0 $? I've seen proofs that set $a_n = \lambda^{n-d} , \lambda \neq 0$, but why? And another question is if this characteristic polynomial has anything to do with the characteristic polynomial used to determine eigenvalues of a matrix. Thanks!

Answer 1

To answer your last question first, yes it does. Consider the vector $\mathbf{a}_n = \begin{matrix}(a_n & a_{n-1} & \ldots & a_{n-d})^T\end{matrix}$. Then you can write the recurrence relation as:

$\mathbf{a}_{n+1} = \begin{bmatrix} c_1 & c_2 & \ldots & c_{d-1} & c_d \\ 1 & 0 & \ldots & 0 & 0 \\ 0 & 1 & \ldots & 0 & 0 \\ & & \ddots \\ 0 & 0 & \ldots & 1 & 0 \end{bmatrix} \mathbf{a}_n$

and you can, with some appropriate transformations, relate the characteristic polynomial of that matrix to the one of the recurrence.

Then, if you can express $\mathbf{a}_0$ as a linear combination of the eigenvectors of the matrix, i.e. $\mathbf{a}_0 = \alpha_1 \mathbf{v}_1 + \ldots + \alpha_d \mathbf{v}_d$, you can show that $\mathbf{a}_n = \alpha_1 \lambda_1^n \mathbf{v}_1 + \ldots + \alpha_n \lambda_d^n \mathbf{v}_d$, giving you a closed form for the sequence.

The conditions you've asked about are about setting everything up so that you can actually have such a relationship.