Texts about the theoretical background of systems of linear recurrence equations I'm looking for books/texts which develop some theory for systems of linear recurrence equations, if possible with   focus on solvability and uniqueness (and whether or not the methods will always work).
So far I had no luck finding such references. I found a few examples in a few books, e.g. in "Foundations of Combinatorics with Applications" by Bender, which has a chapter on them, but without developing any theory regarding them.
 A: You can reduce solving such things to taking powers of matrices, as follows (this is true even if there's only one recurrence, which is a useful thing to know about linear recurrences). It's a little tedious to write down the most general possible thing so let me just indicate the idea with an example. Suppose your system looks like
$$a_n = b_{n-1} + c_{n-2}$$
$$b_n = 2 a_{n-1} + a_{n-2} + c_{n-1}$$
$$c_n = a_{n-2} + 2 c_{n-1}.$$
Your goal is to rewrite the system so that it's a system of first-order recurrences - that is, so that only the index $n-1$ appears on the RHS. You do this by introducing new recurrences given by shifted versions of the old recurrences. In this case, we need to introduce new recurrences $d_n = a_{n-1}$ and $e_n = c_{n-1}$, which produces a new system
$$a_n = b_{n-1} + e_{n-1}$$
$$b_n = 2 a_{n-1} + d_{n-1} + c_{n-1}$$
$$c_n = d_{n-1} + 2 c_{n-1}$$
$$d_n = a_{n-1}$$
$$e_n = c_{n-1}$$
which can be written in matrix form as follows. Write $v_n = \left[ \begin{array}{c} a_n \\ b_n \\ c_n \\ d_n \\ e_n \end{array} \right]$; then the above system can be written
$$v_n = \left[ \begin{array}{ccccc} 0 & 1 & 0 & 0 & 1 \\ 2 & 0 & 1 & 1 & 0 \\ 0 & 0 & 2 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{array} \right] v_{n-1}.$$
Write $M$ for the matrix in the above equation. Then we have
$$\boxed{ v_n = M^n v_0. }$$
