Proof that geometric solutions come from roots of the characteristic polynomial

Proof

1. Let $E$ have order $d$ and coefficients $c_0, \dots, c_{d-1} \in R$. It is a linear recurrence with constant coefficients. Let $u_n = q^n$ for $n \in \N$, with $q^0 = 1$.
2. By the definition of the characteristic polynomial, $\chi_E(q) = q^d - \sum_{i=0}^{d-1} c_i q^i$.
3. For each $n \in \N$, since $R$ is commutative, $$u_{n+d} - \sum_{i=0}^{d-1} c_i\, u_{n+i} = q^n q^d - \sum_{i=0}^{d-1} c_i\, q^n q^i = q^n\, \chi_E(q).$$
4. By the definition of a solution, $(u_n)$ solves $E$ exactly when the left side of step 3 is $0$ for every $n \in \N$.
5. Suppose $(u_n)$ is a solution. Step 3 with $n = 0$ gives $0 = q^0 \chi_E(q) = \chi_E(q)$. So $q$ is a root of $\chi_E$.
6. Conversely, suppose $\chi_E(q) = 0$. Then step 3 gives $q^n \chi_E(q) = 0$ for every $n$. By step 4, $(q^n)_{n \ge 0}$ is a solution of $E$.