Basis of Solutions of a Difference Equation¶

Definition¶

Consider the homogeneous linear difference equation of order $k$ with constant coefficients and $a_0\ne0$$0$,

Its solutions form a subspace $S$ of the vector space of real sequences. A basis of solutions (fundamental set) is a list of solutions $y^{(1)},\ldots,y^{(k)}$ that is a basis of $S$: the sequences are linearly independent, and every solution can be written uniquely as

This expression with arbitrary constants $c_1,\ldots,c_k$ is the general solution.

Interpretation¶

Linearity makes sums and scalar multiples of solutions again solutions, so the solution set is a vector space. Its dimension is $k$ because a solution is fixed by its $k$ initial values: the map $x\mapsto(x_0,\ldots,x_{k-1})$ is a linear bijection from $S$ onto $\mathbb{R}^k$. A basis therefore gives coordinates $(c_1,\ldots,c_k)$ for every possible trajectory, and fitting initial values means solving a $k\times k$ linear system.

The figure uses the first example, $x_{t+2}-3x_{t+1}+2x_t=0$$0$. Its basis solutions are the constant sequence $y^{(1)}_t=1$ and $y^{(2)}_t=2^t$$2^t$. The initial values $x_0=5$$5$, $x_1=7$ fix the coordinates $c_1=3$$3$, $c_2=2$$2$, and the green trajectory $x_t=3y^{(1)}_t+2y^{(2)}_t=3+2^{t+1}$ follows: $5,7,11,19$. Other initial values give other coordinates for the same two basis sequences.

The standard basis comes from the characteristic polynomial. A common error is to take fewer than $k$ sequences, for example only $r^t$ for a double root $r$; the list then spans a proper subspace and cannot match all initial values. Another is to take $k$ sequences that are multiples of each other, such as $2^t$ and $3\cdot2^t$$2^t$, which are dependent.

The inhomogeneous equation has no basis of solutions: its solution set is the affine subspace "particular solution $+\,S$".

Key Results¶

• $\dim S=k$$k$; any $k$ linearly independent solutions form a basis.
• $k$ solutions form a basis if and only if their vectors of initial values $\big(y^{(j)}_0,\ldots,y^{(j)}_{k-1}\big)$, $j=1,\ldots,k$$1,\dots ,k$, are linearly independent, that is, the $k\times k$ matrix with these vectors as columns has nonzero determinant.
• If the roots $r_1,\ldots,r_k$ are distinct, $r_1^t,\ldots,r_k^t$ is a basis (the matrix of initial values is a Vandermonde matrix).
• A root $r$ of multiplicity $m$ contributes $r^t,tr^t,\ldots,t^{m-1}r^t$; a nonreal pair $\rho \mathrm{e}^{\pm\mathrm{i}\theta}$ may be replaced by $\rho^t\cos(\theta t),\ \rho^t\sin(\theta t)$.

Examples¶

Fitting initial values. For $x_{t+2}-3x_{t+1}+2x_t=0$ the roots are $1$ and $2$, so $y^{(1)}_t=1$$1$, $y^{(2)}_t=2^t$$2^t$, and the matrix of initial values has $\det\begin{pmatrix}1&1\\1&2\end{pmatrix}=1\ne0$$0$. For $x_0=5$$5$, $x_1=7$$7$: $c_1+c_2=5$$5$, $c_1+2c_2=7$$7$, so $c_2=2$$2$, $c_1=3$ and $x_t=3+2^{t+1}$$2^{t+1}$. Check: $x_2=11=3\cdot7-2\cdot5$$5$.

Repeated root. For $x_{t+2}-4x_{t+1}+4x_t=0$ take $2^t$ and $t\,2^t$. Their matrix of initial values has $\det\begin{pmatrix}1&0\\2&2\end{pmatrix}=2\ne0$$0$, so they form a basis.

Not a basis. $2^t$ and $3\cdot2^t$ both solve the previous equation, but $\det\begin{pmatrix}1&3\\2&6\end{pmatrix}=0$$0$: they are dependent and cannot produce the solution with $x_0=0$$0$, $x_1=1$$1$.

Prerequisites¶

• Characteristic Polynomial for a Difference Equation
• Linear Dependence and Independence
• Basis
• Determinant

Related Concepts¶

• Higher-Order Linear Difference Equation
• Second-Order Linear Difference Equation
• System of Linear Difference Equations
• General Solution of a Linear ODE

Sources¶

• Math V: Advanced Linear Algebra · Week 2

Aliases: fundamental set of solutions, fundamental system of solutions, solution basis of a recurrence Keywords: dimension of the solution space is k, general solution c_1 r_1^t + ... + c_k r_k^t Symbols: real numbers, rho, theta

Last updated: 14 October 2026 08:21