# A two variable sequence

I am having trouble with (a)

I am thinking about showing the following, $(x_{n+1},y_{n+1}) \geq (x_n,y_n)$ So being more explicit, I get

$\left ( \sqrt{\dfrac{x^2_n + 2y^2_n}{4}}, \dfrac{x_n + y_n + 1}{3}\right )\geq (x_n,y_n)$

So working out the first few steps of the algebra, I get

$$\left ( \dfrac{x^2_n + 2y^2_n}{4}, \dfrac{x_n + 1}{3}\right )\geq (x_n^2,\dfrac{2y_n}{3})$$ $$\left ( -3x^2_n + 2y^2_n, \dfrac{x_n + 1}{3}\right )\geq (0,\dfrac{2y_n}{3})$$ $$\left ( 2y_n^2, -2y_n\right )\geq (3x_n^2,-(x_n + 1))$$

And now I am stuck...

-

The proof of (a) is by induction. There is not quite increase always, since $x_1=0$. But we can compute a step further, and show that $x_2\gt x_1$ and $y_2\gt y_1$.

Assume that $k \ge 1$, and $x_{k+1}\gt x_k$ and $y_{k+1}\gt y_k$. We prove that $x_{k+2}\gt y_{k+1}$ and $y_{k+2}\gt y_{k+1}$.

This is relatively easy. For ease of typing, we deal with the $y$'s. We have $y_{k+2}=\frac{x_{k+1}+y_{k+1}+1}{3}$. But by the induction assumption, we have $x_{k+1}\gt x_k$ and $y_{k+1}\gt y_k$. It follows that $$y_{k+2}=\frac{x_{k+1}+y_{k+1}}{3}\gt \frac{x_k+y_k+1}{3}=y_{k+1}.$$

The argument for $x_{k+2}$ is very similar.

For boundedness, we prove by induction that $x_n \lt 1$ and $y_n \lt 1$ for all $n$. The two inuction steps are quite straightforward.

Because our two sequences $(x_n)$ and $(y_n)$ are non-decreasing and bounded above, they each have a limit.

As to the limits, if $x$ is the limit of the $x_n$, and $y$ is the limit of the $y_n$, we have $x=\sqrt{\frac{x^2+2y^2}{4}}$ and $y=\frac{x+y+1}{3}$. If we square both sides of the first equation, we obtain an expression of $y$ in terms of $x$. Substituting for $x$ in the second equation, we find $y$. Then we compute $x$.

-
For boundness, I just picked an arbitrary number "M", why did you choose 1? –  Hawk Oct 23 '12 at 4:43
Because a look at the recurrence shows that this works. The number $M$ cannot be quite arbitrary. If you assume, for example, that $x_k$ and $y_k$ are each $\lt 1/10$, you will not be able to prove that $y_{k+1}\lt 1/10$. We do need to pick something that will let the induction go through. –  André Nicolas Oct 23 '12 at 4:50
So basically it's trial and error –  Hawk Oct 23 '12 at 4:51
Well, for the boundedness I only tried one thing. If you try to prove by induction that $x_n\lt 5$ and $y_n\lt 5$ for all $n$, that will be equally easy. I don't really like $M$ because (i) some $M$ don't work and (ii) these are two concrete numerical sequences, I should be able to come up with a concrete bound. –  André Nicolas Oct 23 '12 at 4:56