---
tag: K00NJY6C33
kind: statement
role: theorem
name: Dimension of the solution space of a linear recurrence
msc: [39A06, 15A03]
uses: [081THG13JZ, 05BDYVQQ0T, 05G2G0P224]
about: [099GXMHV40]
sources:
  - url: https://en.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficients
---

## Statement

Let $K$ be a field, let $d \ge 0$ be an integer, and let $c_0, \dots, c_{d-1} \in K$.
Let $E$ be the [[linear recurrence with constant coefficients|081THG13JZ]] $u_{n+d} = c_0 u_n + c_1 u_{n+1} + \dots + c_{d-1} u_{n+d-1}$ $(n \ge 0)$.
Then the [[space of solutions|05BDYVQQ0T]] of $E$ is a $K$-vector space of [[dimension|05G2G0P224]] $d$.

## 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$.

## Explanations

### L1 human

A linear recurrence of order $d$ has as many independent solutions as it has starting values.
Any solution is a combination of $d$ basic solutions.
So to solve such a recurrence completely, it is enough to find $d$ solutions that are independent.

### L2 human

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|0BWDJGQYST]].
By the theorem on [[geometric solutions|096SD4ERQH]], 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.