Space of solutions of a linear recurrence

Definition

Let $R$ be a commutative ring, and let $E$ be a linear recurrence with constant coefficients over $R$ of order $d$. The space of solutions of $E$ is the set of all solutions of $E$. It is a submodule of the $R$-module $R^{\mathbb{N}}$ of all sequences in $R$, with termwise addition and scalar multiplication.

Remarks

The map $u \mapsto (u_0, \dots, u_{d-1})$ is an isomorphism of $R$-modules from the space of solutions to $R^d$. Over a field, the space of solutions has dimension $d$. For the Fibonacci recurrence over $\mathbb{R}$, the sequences $\varphi^n$ and $\psi^n$ form a basis, with $\varphi$ and $\psi$ the roots of $X^2 - X - 1$.

Explanations

L1 human

If two sequences solve the same linear recurrence, then so does their sum, and so does any multiple of one of them. So the solutions form a vector space, and the first $d$ terms are coordinates on it.