Higher-Order Linear Difference Equation¶

Definition¶

A linear difference equation of order $k$ with constant coefficients is

x_{t+k}+a_{k-1}x_{t+k-1}+\cdots +a_1x_{t+1}+a_0x_t=g_t,

for $t=0,1,2,\ldots$ $0, 1, 2, \dots$ , with real constants $a_0,\ldots,a_{k-1}$ , $a_0\ne0$ $0$ , and a given sequence $(g_t)$ . With the state vector $\boldsymbol{y}_t=(x_t,x_{t+1},\ldots,x_{t+k-1})^{\top}\in\mathbb{R}^k$ it is equivalent to the first-order system

\begin{aligned} \boldsymbol{y}_{t+1}&=C\boldsymbol{y}_t+g_t\boldsymbol{e}_k,\\ C&=\begin{pmatrix}0&1&\cdots&0\\\vdots&\vdots&\ddots&\vdots\\0&0&\cdots&1\\-a_0&-a_1&\cdots&-a_{k-1}\end{pmatrix}, \end{aligned}

where $C$ is the companion matrix and $\boldsymbol{e}_k$ the last standard basis vector.

Interpretation¶

The second-order equation generalizes directly: the next value uses the $k$ most recent values, so $k$ initial values $x_0,\ldots,x_{k-1}$ are needed. The homogeneous equation is solved by the roots of the characteristic polynomial $p(r)=r^k+a_{k-1}r^{k-1}+\cdots+a_0$ $a_{0}$ , now of degree $k$ , so for $k\ge3$ the roots may be harder to find and a factor is often guessed first (with integer coefficients, every integer root divides $a_0$ ).

The companion form shows why difference equations belong to linear algebra. The first $k-1$ rows of $C$ only shift the window forward one period; the last row is the equation itself. Iterating is repeated matrix multiplication, $\boldsymbol{y}_t=C^t\boldsymbol{y}_0$ in the homogeneous case, and $\det(\lambda I-C)=p(\lambda)$ $p (λ)$ , so the characteristic roots are the eigenvalues of $C$ .

A common slip is to write the last row of $C$ with $+a_i$ instead of $-a_i$ : the signs flip because $x_{t+k}$ is isolated on the left.

Key Results¶

Every choice of $x_0,\ldots,x_{k-1}$ gives exactly one solution; the homogeneous solutions form a $k$ -dimensional space with a basis of solutions built from the characteristic roots.
A root $r$ of multiplicity $m$ contributes $r^t,tr^t,\ldots,t^{m-1}r^t$ .
General solution = particular solution + general homogeneous solution; for $g_t=b$ and $p(1)\ne0$ the equilibrium $x^*=b/p(1)$ is a particular solution.
$\det C=(-1)^k a_0\ne0$ $0$ , so $C$ is invertible.
All solutions converge to $x^*$ if and only if every characteristic root has modulus less than $1$ (stability).

Examples¶

Third order, distinct roots. $x_{t+3}-6x_{t+2}+11x_{t+1}-6x_t=0$ has $p(r)=r^3-6r^2+11r-6=(r-1)(r-2)(r-3)$ $3)$ , so $x_t=c_1+c_2 2^t+c_3 3^t$ $c_{3} 3^{t}$ . For $x_0=0$ $0$ , $x_1=1$ $1$ , $x_2=5$ $5$ :

c_1+c_2+c_3=0,\qquad c_1+2c_2+3c_3=1,\qquad c_1+4c_2+9c_3=5,

giving $c_1=0$ $0$ , $c_2=-1$ $- 1$ , $c_3=1$ and $x_t=3^t-2^t$ $2^{t}$ . Check: $x_3=19=6\cdot5-11\cdot1+6\cdot0$ $0$ . The companion matrix is $C=\begin{pmatrix}0&1&0\\0&0&1\\6&-11&6\end{pmatrix}$ $006 10 - 11 016$ , with eigenvalues $1,2,3$ .

A row of the sequence values x0 = 0, x1 = 1, x2 = 5, x3 = 19, x4 = 65, with braces marking the state window y0 and the shifted window y1 = Cy0 that adds x3.

The state $\boldsymbol{y}_t$ is a window of three consecutive values. In the figure, $\boldsymbol{y}_0=(0,1,5)^{\top}$ is bracketed above the row and $\boldsymbol{y}_1=C\boldsymbol{y}_0=(1,5,19)^{\top}$ below it: the first two rows of $C$ copy $x_1$ and $x_2$ one place forward, and the last row produces the new value $x_3=6\cdot5-11\cdot1+6\cdot0=19$ $19$ . Repeating the step gives $x_4=65=3^4-2^4$ $2^{4}$ .

Triple root. $x_{t+3}-3x_{t+2}+3x_{t+1}-x_t=0$ has $p(r)=(r-1)^3$ $1)^{3}$ , so $x_t=c_1+c_2t+c_3t^2$ $c_{3} t^{2}$ : exactly the sequences whose third differences vanish.

Prerequisites¶

Sources¶

Math V: Advanced Linear Algebra · Week 2

Aliases: Higher Order Linear Difference Equation, kth-order linear difference equation, linear recurrence of order k, linear difference equation of order k, nth-order linear difference equation Keywords: companion matrix, state vector (x_t, x_{t+1}, ..., x_{t+k-1}), k initial values, reduction to a first-order system Symbols: element of, lambda, real numbers

Last updated: 22 October 2026 19:04