5

We have an inductively defined sequence $x_n=x_{n-1}+2y_{n-1}$ and $y_n=x_{n-1}+y_{n-1}$ where $x_n^2-2y_n^2=\pm 1$, where $x_0=1$ and $y_0=0$.

I need to prove that the sequence $\left(\frac{x_n}{y_n}\right)_{n=1}^\infty$ converges to $\sqrt2$.

Now I can see that $\left(\frac{x_n^2}{y_n^2}\right)_{n=1}^\infty$ converges to $2$, so that may be easier to prove.

It follows now that in order to prove this, $\forall\epsilon >0, \exists n>N$ s.t. $|\frac{x_n^2}{y_n^2}-2|<\epsilon$.

Can anybody point me in the right direction for solving this?

duncster94
  • 359

2 Answers2

2

That is not an equivalent statement. For example, $\{ (-1)^n \}$ doesn't converge, but the sequence of squares of each term converges to 1.

You will need to make an argument about the positive or negative nature of each term too. Once you've done that

Hint: $\frac {x_n ^2}{y_n^2} - 2 = \pm \frac {1}{y_n^2}$, and $y_n \rightarrow \pm \infty$, depending on your initial conditions.

Calvin Lin
  • 68,864
  • 1
    Hmm I see, but wouldn't this be an equivalent statement based on the fact that $x_n$ and $y_n$ are always positive? – duncster94 Jan 16 '13 at 23:36
  • @DuncanForster Considering that you didn't set any initial conditions, we could have $x_1 = -1, y_1=-1$, in which case we'd have $y_n \rightarrow -\infty$. In fact, it's possible for the terms to be oscillating ... The initial conditions are important. – Calvin Lin Jan 17 '13 at 02:43
  • Sorry I should have specified, $x_0=1$ and $y_0=0$. – duncster94 Jan 17 '13 at 03:42
  • @DuncanForster You should edit that into the original equation then. If you look at rob john's solution, you will find that there are initial conditions that lead to a different convergence. – Calvin Lin Jan 17 '13 at 16:20
2

The recursion can be written as $$ \begin{bmatrix}x_n\\y_n\end{bmatrix}=\begin{bmatrix}1&2\\1&1\end{bmatrix}\begin{bmatrix}x_{n-1}\\y_{n-1}\end{bmatrix} $$ The matrix has two eigenvalues: the roots of $\lambda^2-2\lambda-1=0$; that is, $\lambda=1\pm\sqrt{2}$.

The eigenvector with the eigenvalue of $1-\sqrt{2}$ is $$ \begin{bmatrix}1&2\\1&1\end{bmatrix}\color{#C00000}{\begin{bmatrix}\sqrt{2}\\-1\end{bmatrix}}=\begin{bmatrix}-2+\sqrt{2}\\-1+\sqrt{2}\end{bmatrix}=(1-\sqrt{2})\color{#C00000}{\begin{bmatrix}\sqrt{2}\\-1\end{bmatrix}} $$ The eigenvector with the eigenvalue of $1+\sqrt{2}$ is $$ \begin{bmatrix}1&2\\1&1\end{bmatrix}\color{#C00000}{\begin{bmatrix}\sqrt{2}\\1\end{bmatrix}}=\begin{bmatrix}2+\sqrt{2}\\1+\sqrt{2}\end{bmatrix}=(1+\sqrt{2})\color{#C00000}{\begin{bmatrix}\sqrt{2}\\1\end{bmatrix}} $$ Therefore, $$ \begin{align} \begin{bmatrix}x_n\\y_n\end{bmatrix} &=\begin{bmatrix}x_0\\y_0\end{bmatrix}\begin{bmatrix}1&2\\1&1\end{bmatrix}^n\\ &=\left(a\begin{bmatrix}\sqrt{2}\\1\end{bmatrix}+b\begin{bmatrix}\sqrt{2}\\-1\end{bmatrix}\right)\begin{bmatrix}1&2\\1&1\end{bmatrix}^n\\ &=a(1+\sqrt2)^n\begin{bmatrix}\sqrt{2}\\1\end{bmatrix}+b(1-\sqrt2)^n\begin{bmatrix}\sqrt{2}\\-1\end{bmatrix}\\ &=a(1+\sqrt2)^n\left(\color{#C00000}{\begin{bmatrix}\sqrt{2}\\1\end{bmatrix}+\frac{b}{a}(2\sqrt{2}-3)^n\begin{bmatrix}\sqrt{2}\\-1\end{bmatrix}}\right) \end{align} $$ Assuming $a\ne0$, what is the limit of $x_n/y_n$ in red?

robjohn
  • 345,667