Dimension of the solution space of a linear recurrence

Remarks

The map $u \mapsto (u_0, \dots, u_{d-1})$ from the space of solutions to $K^d$ is linear. It is injective, because the recurrence computes every later term from the first $d$ terms, and surjective, because any choice of first terms extends to a solution. So it is an isomorphism, and the dimension is $d$. Example: for the Fibonacci recurrence $u_{n+2} = u_{n+1} + u_n$ over $\R$, the space has dimension $2$. A basis is given by the solutions that start $(1, 0)$ and $(0, 1)$, or by $\varphi^n$ and $\psi^n$ with $\varphi, \psi = \frac{1 \pm \sqrt{5}}{2}$. The same argument works for a linear difference equation with variable coefficients $a_k(n) u_{n+k} + \dots + a_0(n) u_n = 0$, provided $a_k(n) \ne 0$ for all $n$.

Going deeper

For a student

The theorem is the discrete analogue of the fact that a linear differential equation of order $d$ has a $d$-dimensional space of solutions. In practice, one finds a basis from the roots of the characteristic polynomial. By the theorem on geometric solutions, each root $q$ gives the solution $q^n$. In characteristic $0$, a nonzero root $q$ of multiplicity $m$ gives the solutions $n^j q^n$ for $j < m$. When $c_0 \ne 0$ and the characteristic polynomial splits over $K$, these $d$ sequences are independent, so the dimension count shows they form a basis. The general solution of an inhomogeneous equation is one particular solution plus an element of this space.