Is it possible to convert a higher order difference equation to a system of lower order difference equations?

Question

I know this is possible for differential equations. But is there a similar result for difference equations?

So I was thinking of going from a higher order difference equation describing a single sequence to a system of first order equation describing multiple sequences.

Answer 1

It seems yes. Consider the second order system $u_{n+1} = u_n+u_{n-1}$ (i.e. Fibonacci).

Define $k_n = u_{n-1}$.

This gives two sequences $u_n$ and $k_n$. And the system of first order equations governing these is $u_{n+1} = u_n + k_n$ and $k_{n+1} = u_n$.

So indeed we see a similar result.