Linear difference equation

Remarks

Since $a_k(n) \ne 0$, the equation can be solved for $u_{n+k}$, so it is a recurrence relation 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 $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.