Solving a system of three recurrence relations

Question

I am working with a computer algebra system to solve a system of recurrence relations. In order to solve a system of two recurrence relations, the guide mentions that the program

"cannot directly solve a system of recurrence relations. In order to do so, the system must be re-written as a single higher-order relation"

It goes on to say, for example:

$y(n+1) = 2y(n) + z(n)$

$z(n+1) = z(n) + y(n)$

Must be re-written as:

$y(n+2) = 2y(n+1) + z(n+1)$

$y(n+1) = 2y(n) + z(n)$

$z(n+1) = z(n) + y(n)$

... which may then be solved with $y(n+2), z(n+1), z(n)$ regarded as the three unknowns.

In really simple terms, could someone explain:

1. What rule one must use to transform the given system into a single higher order system as this is not immediately apparent in the example above
2. What are the unknowns to solve in this re-written system

My ultimate question is, using the explanation above and by way of practical example, how would you rewrite the following system and what would be the unknowns of the re-written system?

$x(n+1) = 2x(n) + y(n) - z(n)$

$y(n+1) = x(n) - 2y(n) - z(n)$

$z(n+1) = \frac{x(n)}{2} + \frac{y(n)}{3} - \frac{z(n)}{4}$

Answer 1

I am not sure what exact format the program wants you to put your formulas in, but let me show a way of solving your system. Note that it can be rewritten as $$ \begin{bmatrix} x_{n+1} \\ y_{n+1} \\ z_{n+1} \end{bmatrix} = \begin{bmatrix} 2 & 1 & -1 \\ 1 &-2 &-1 \\ \frac{1}{2} & \frac{1}{3} & \frac{1}{4} \end{bmatrix} \begin{bmatrix} x_{n} \\ y_{n} \\ z_{n} \end{bmatrix}. $$ Call the multiplcication matrix A. Then we can rewrite A using an eigendecomposition $A = Q\Lambda Q^{-1}$. It follows that $$ \begin{bmatrix} x_{n} \\ y_{n} \\ z_{n} \end{bmatrix} = (Q\Lambda Q^{-1})^n \begin{bmatrix} x_{1} \\ y_{1} \\ z_{1} \end{bmatrix} = Q\Lambda^n Q^{-1} \begin{bmatrix} x_{1} \\ y_{1} \\ z_{1} \end{bmatrix}. $$ The eigendecomposition can be easily obtained with any statistical software. Matlab gives \begin{align} \Lambda &= \begin{bmatrix} -2.1757 & 0 & 0\\ 0 & 1.8130 & 0\\ 0 & 0 & 0.6127 \end{bmatrix} \\ Q &= \begin{bmatrix} -0.2504 & 0.9304 & 0.6143\\ 0.9647 & 0.1572 & -0.0659\\ -0.0810 & 0.3312 & 0.7863 \end{bmatrix}. \end{align}