Solving recurrence with vectors

Question

I am trying to learn more about how to model questions about recurrence relations using matrices. How would one approach the following problem:

"Suppose $y_n$ and $x_n$ satisfy:

$\begin{bmatrix}x_{n}\\y_{n}\end{bmatrix}$ = $\begin{bmatrix}2 & 1\\1 & 1\end{bmatrix}$ $\begin{bmatrix}x_{n-1}\\y_{n-1}\end{bmatrix}$

with $x_0 = y_0 = 1$. What is $\text{lim}_{n \rightarrow \infty} \frac{x_n}{y_n}$ assuming this limit exists?"

I am not used to seeing a recurrence expressed in this way. The author mentions a "standard trick," which I am also unaware of.

Answer 1

As $A = \left( \begin{array}{cc} 2 & 1 \\ 1 & 1 \\ \end{array} \right) = T\cdot\Lambda\cdot T^{-1}$ with $T = \left( \begin{array}{cc}\frac{1}{2} \left(1+\sqrt{5}\right) & \frac{1}{2} \left(1-\sqrt{5}\right) \\ 1 & 1 \\ \end{array} \right)$ and $\Lambda =\left( \begin{array}{cc} \frac{1}{2} \left(3+\sqrt{5}\right) & 0 \\ 0 & \frac{1}{2} \left(3-\sqrt{5}\right) \\ \end{array} \right)$ we have

$$ X_n = T\cdot\Lambda\cdot T^{-1}X_{n-1} $$

or

$$ T^{-1}X_{n} = \Lambda\cdot T^{-1}X_{n-1} $$

now calling $Y_n = T^{-1}X_{n}$ we follow with

$$ Y_n = \Lambda Y_{n-1} $$

with solution

$$ Y_n = \Lambda^n\cdot Y_0 $$

hence

$$ X_n = T\cdot\Lambda^n\cdot T^{-1}X_0 $$

Here $\Lambda^n = \left( \begin{array}{cc} \left(\frac{1}{2} \left(3+\sqrt{5}\right)\right)^n & 0 \\ 0 & \left(\frac{1}{2} \left(3-\sqrt{5}\right)\right)^n \\ \end{array} \right)$

Answer 2

Note that in this specific case $$\begin{bmatrix}2&1\\1&1\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^2,$$ so that the solution can be expressed in terms of the Fibonacci sequence (with $F_{-1},F_0,F_1,F_2=1,0,1,1$). One can test that the sequence $$ z_0=y_0,~~z_1=x_0,~~~z_{n+2}=z_{n+1}+z_n\\ \implies z_n=x_0F_n+y_0F_{n-1} $$ gives the solution of the original task as $$ x_n=z_{2n+1}~\text{ and }~ y_n=z_{2n} $$

This gives the ratio as $$ \frac{x_n}{y_n}=\frac{x_0F_{2n+1}+y_0F_{2n}}{x_0F_{2n}+y_0F_{2n-1}} \xrightarrow{n\to\infty} \frac{x_0\phi+y_0}{x_0+y_0(\phi-1)} $$