---
tag: 5115KV924G
kind: definition
name: Linear difference equation
msc: [39A06]
defines: AA7XRZ4VAG
uses: [07TZV87Y0T, 0QA8CHH8MG]
sources:
  - url: https://en.wikipedia.org/wiki/Linear_recurrence_with_constant_coefficients
---

## Definition

Let $K$ be a [[field|0QA8CHH8MG]] and let $k \ge 1$ be an integer.
Let $a_0, a_1, \dots, a_k$ and $b$ be sequences in $K$, indexed by $n \in \N$, with $a_k(n) \ne 0$ for all $n$.
The *linear difference equation* with these coefficients is the equation
$$a_k(n)\, u_{n+k} + a_{k-1}(n)\, u_{n+k-1} + \dots + a_0(n)\, u_n = b(n) \qquad (n \ge 0)$$
for an unknown sequence $(u_n)_{n \ge 0}$ in $K$.
It is *homogeneous* if $b(n) = 0$ for all $n$, and *inhomogeneous* otherwise.
It has *constant coefficients* if each $a_i$ is a constant sequence.

## Remarks

Since $a_k(n) \ne 0$, the equation can be solved for $u_{n+k}$, so it is a [[recurrence relation|07TZV87Y0T]] of order at most $k$.
Example: $u_{n+1} - (n+1) u_n = 0$ is a homogeneous linear difference equation with $k = 1$, $a_1 = 1$ and $a_0(n) = -(n+1)$; with $u_0 = 1$ its solution is $u_n = n!$.
Non-example: $u_{n+1} = u_n^2$ is not linear, because the unknown appears squared; the sequences $u = (1, 1, 1, \dots)$ and $2u = (2, 2, 2, \dots)$ show that multiples of solutions need not be solutions.
In terms of the [[shift operator|91QMF4R1CY]] $E$, the equation reads $L u = b$ with $L = a_k E^k + \dots + a_0$, a linear operator on sequences.
The constant coefficient case is the [[linear recurrence with constant coefficients|081THG13JZ]].