The Lost Notebooks - I : Transforming a System of Linear Recurrences of Order 1 into (two) Linear Recurrences of Order 2

          Let the sequences  $(x_n)_{n\in \mathbb{Z}},\;(y_n)_{n\in \mathbb{Z}}$  be defined by the relations 

\begin{cases}x_{n+1}=a\cdot x_n+b\cdot y_n\;\;\;\;(1)\\y_{n+1}=c \cdot x_n+d \cdot y_n\;\;\;\;\;(2) \end{cases}

To determine them, an "initial" value needs to be given, for example $x_0$ and  $y_0$.

          We show that we can write a recurrence relation for each of the sequences in (1), (2), surprisingly (or NOT ?) the same.

$$x_{n+2}=(a+d)\cdot x_{n+1}-(ad-bc)\cdot x_n\;\;;\;\;y_{n+2}=(a+d)\cdot y_{n+1}-(ad-bc)\cdot y_n \tag{3}$$

To determine exactly each of the sequences $(x_n)_{n\in \mathbb{Z}},\;(y_n)_{n\in\mathbb{Z}}$, two "initial" values ​​need to be given, for example $x_0$ and $x_1$ &c.

                       Proof  CiP (with the necessary clumsiness)

               $x_{n+2}\;\overset{(1)}{\underset{\overbrace{n\to n+1}}{=}}\;a\cdot x_{n+1}+b\cdot y_{n+1}\overset{(2)}{=}\;a\cdot x_{n+1}+b\cdot (          c\cdot x_n+d\cdot y_n)=$

$=a\cdot x_{n+1}+bc\cdot x_n+bd\cdot y_n\;$

$\Rightarrow \;\;\;bd \cdot y_n=x_{n+2}-a\cdot x_{n+1}-bc\cdot x_n \tag{4}$

Later $d\cdot x_{n+1}\overset{(1)}{=}ad\cdot x_n+bd\cdot y_n \overset{(4)}{=}ad\cdot x_n+x_{n+2}-a\cdot x_{n+1}-bc\cdot x_n\;\;\Rightarrow$

$\Rightarrow\;\;\;x_{n+2}=(a+d)\cdot x_{n+1}-(ad-bc)\cdot x_n\;;$ the first formula (3) is proven. 

     From (2) written for $n+1$, it follows

$y_{n+2}-d\cdot y_{n+1}=c\cdot x_{n+1}\overset{(1)}{=}c\cdot(a\cdot x_n+b\cdot y_n)\;\overset{\underbrace{c\cdot x_n=from\;(2)}}{=}a\cdot (y_{n+1}-d\cdot y_n)+bc\cdot y_n=$

$=a\cdot y_{n+1}-(ad-bc)\cdot y_n$

and from the extreme equalities the second part of (3) results.

$\blacksquare$

          Remark CiP  The matrix $M=\begin{pmatrix}a&b\\c&d\\\end{pmatrix}$ that appears in (1)&(2) has the characteristic polynomial $P(\lambda)=\lambda^2-(a+d)\cdot \lambda+(ad-bc)$, which coincides with the characteristic polynomial of the recurrences (3).

<end Rem>

          An example is shown in the images below. (In the second image, with the red color, I made the mistake of eliminating $x_n$ and obtained for $y_n$ a recurrence relation of order 3 - in formula (4) there. This turned out to be just an illusion...)