---
tag: 7ZQPD24050
kind: proof
name: Proof that geometric solutions come from roots of the characteristic polynomial
msc: [39A06]
proves: 096SD4ERQH
uses: [081THG13JZ, 0ZV2YKKZ58, 0BWDJGQYST]
sources:
  - url: https://en.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficients
    locator: Characteristic polynomial and roots
---

## 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|081THG13JZ]]. Let $u_n = q^n$ for $n \in \N$, with $q^0 = 1$.
2. By the definition of the [[characteristic polynomial|0BWDJGQYST]], $\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|0ZV2YKKZ58]], $(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$.

## Idea

Plug $q^n$ into the recurrence. Every term has the common factor $q^n$, and what remains is exactly $\chi_E(q)$.
At $n = 0$ the factor is $1$, so the recurrence holds for all $n$ exactly when $\chi_E(q) = 0$.