0
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ The quotient $x_n/x_{n-1}$ approaches exactly $3+2\sqrt{2}$. $\endgroup$ Dec 23, 2017 at 11:17

2 Answers 2

1
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.