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$ ,

x_{t+k}+a_{k-1}x_{t+k-1}+\cdots+a_0x_t=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

x_t=c_1y^{(1)}_t+\cdots+c_ky^{(k)}_t.

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.

Plot over t = 0 to 3 of the basis solutions 1 and 2^t and of their combination x_t = 3 + 2^(t+1), which starts at x_0 = 5, x_1 = 7 and grows to 11 and 19.

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 all roots $r_1,\ldots,r_k$ are real and distinct, $r_1^t,\ldots,r_k^t$ is a basis of the real solution space $S$ (the matrix of initial values is a Vandermonde matrix). Over $\mathbb{C}$ , distinct root powers give a basis of complex-valued solutions even when the roots are nonreal.
A real root $r$ of multiplicity $m$ contributes $r^t,tr^t,\ldots,t^{m-1}r^t$ . For a real basis, each nonreal conjugate pair $\rho \mathrm{e}^{\pm\mathrm{i}\theta}$ of multiplicity $m$ contributes $t^j\rho^t\cos(\theta t)$ and $t^j\rho^t\sin(\theta t)$ for $j=0,\ldots,m-1$ $1$ .

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¶

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: complex numbers, real numbers, rho, theta

Last updated: 27 October 2026 11:52