Derive Closed Solution From Two Linear Recurrences

Question

Let $x_0 = y_0 = 1$ and for $n \ge 1$

$x_n = 3x_{n - 1} + 4y_{n - 1}, \\ y_n = 2x_{n - 1} + 3y_{n - 1}.$

Goal. Determine an explicit formula for $x_n$ or $y_n$ just depending on $n$.

Background. These recurrences araise from Pell's equation $x^2 - 2y^2 = -1$. Thus, if we consider

$\displaystyle \left(1 + \sqrt{2}\right)^{2n - 1} = \sum_{k = 0}^{2n - 1} \binom{2n - 1}{k} \left(\sqrt{2}\right)^k$

as an element of $\mathbb{Q}(\sqrt{2})$, it has the form $x_n + y_n\sqrt{2}$. Just from computations, I observed that the quotient $x_{n} / x_{n - 1}$ approaches $5.8284...$ as $n \rightarrow \infty$.

Answer 1

Observe that $$ \begin{pmatrix}x_n\\ y_n\end{pmatrix}=A\begin{pmatrix}x_{n-1}\\ y_{n-1}\end{pmatrix},\text{ where }A=\begin{pmatrix}3&4\\ 2&3\end{pmatrix}. $$ Then $$ \begin{pmatrix}x_n\\ y_n\end{pmatrix}=A^n\begin{pmatrix}1\\ 1\end{pmatrix}. $$ The matrix $A$ has two different eigenvalues $\lambda_\pm=1\pm\sqrt2$, is diagonalizable, $$ A=T\begin{pmatrix}\lambda_+&0\\ 0&\lambda_-\end{pmatrix}T^{-1} $$ for an invertible matrix $T$ and $$ \begin{pmatrix}x_n\\ y_n\end{pmatrix}=T\begin{pmatrix}\lambda_+^n&0\\ 0&\lambda_-^n\end{pmatrix}T^{-1}\begin{pmatrix}1\\ 1\end{pmatrix}. $$ All is left is to compute $T$.

Answer 2

From $x_n=3x_{n-1}+4y_{n-1}$, we have$$y_{n-1}=\frac{x_n-3x_{n-1}}{4}$$ Using this, the second equation becomes $$\frac{x_{n+1}-3x_n}{4}=2x_{n-1}+3\cdot\frac{x_n-3x_{n-1}}{4},$$ i.e. $$x_{n+1}-6x_n+x_{n-1}=0$$

Let $\alpha,\beta\ (\alpha\lt\beta)$ be the solutions of $x^2-6x+1=0$.

Then, we have $$x_{n+1}-\alpha x_{n}=\beta (x_{n}-\alpha x_{n-1})=\cdots =\beta^{n}(x_1-\alpha x_0)$$ $$x_{n+1}-\beta x_{n}=\alpha (x_{n}-\beta x_{n-1})=\cdots =\alpha^{n}(x_1-\beta x_0)$$ Subtracting the latter from the former gives $$(\beta-\alpha)x_{n}=(\beta^{n}-\alpha^{n})x_1+(\alpha^{n}\beta-\alpha\beta^{n})x_0,$$ i.e. $$x_n=\frac{7(\beta^{n}-\alpha^{n})+\alpha^{n}\beta-\alpha\beta^{n}}{\beta-\alpha}$$ and $$y_n=\frac{x_{n+1}-3x_n}{4}$$ where $$\alpha=3-2\sqrt 2,\qquad \beta=3+2\sqrt 2$$

---

Since $\frac{\alpha}{\beta}\lt 1$, we have $$\lim_{n\to\infty}\frac{x_n}{x_{n-1}}=\lim_{n\to\infty}\frac{7-7\left(\frac{\alpha}{\beta}\right)^n+\alpha\left(\frac{\alpha}{\beta}\right)^{n-1}-\alpha}{\frac{7}{\beta}-\frac{7}{\beta}\left(\frac{\alpha}{\beta}\right)^{n-1}+\left(\frac{\alpha}{\beta}\right)^{n-1}-\frac{\alpha}{\beta}}=\frac{7-7\cdot 0+\alpha\cdot 0-\alpha}{\frac{7}{\beta}-\frac{7}{\beta}\cdot 0+0-\frac{\alpha}{\beta}}=3+2\sqrt 2$$