The Invariance Principle

I had come across a problem practicing to get better at approaching different types of problems from different field topics and this one had got me kind of stuck in what direction to go. Not so familiar with the topic, its on invariance's, so I was hoping I can get some assistance on it. The problem is the following.

An algorithm is defined as follows:

$\hspace{1.0in}$ Start: $(x_0,y_0)$ with $~0<x_0<y_0.$

$\hspace{1.0in}$ Step: $x_{n+1}=\dfrac{x_n+y_n}{2}, \hspace{0.4in} y_{n+1}=\sqrt{x_{n+1}y_n.}$

and the arithmetic mean-geometric mean inequality show that

$$x_n<y_n\Rightarrow x_{n+1}<y_{n+1},~~~~~~y_{n+1}-x_{n+1}<\dfrac{y_n-x_n}{4}$$

for all n. Can it be shown that the common limit, $\lim~x_n=\lim~y_n=x=y.$

Thanks.

-
I'm not clear about the title. Where does invariance enter here? – leonbloy Jun 4 '11 at 13:15
I find "$\lim~x_n=\lim~y_n=x=y$" slightly odd. Do you mean "$\text{If }\lim~x_n=x \text{ and } \lim~y_n=y \text { then } x=y$"? – Henry Jun 4 '11 at 13:58
Problem from: math.nyu.edu/~bellova/putnam/putnam09_1.pdf – Zaz Oct 21 '15 at 11:50

If the limits exist: $$\lim_{n \rightarrow \infty}x_{n+1}=\lim_{n \rightarrow \infty}\left(\dfrac{x_n+y_n}{2}\right)$$ $$x=\dfrac{\lim_{n \rightarrow \infty}x_n+\lim_{n \rightarrow \infty}y_n}{2}$$ $$x=\dfrac{x+y}{2}$$ $$x=y$$

-
And you know the limits exist since $x_n \le x_{n+1} \le y_{n+1} \le y_n$ so the $x_n$ sequence is increasing and bounded above, and the $y_n$ sequence is decreasing and bounded below. – Henry Jun 4 '11 at 14:04

For both inequalities you want to prove, you can split the proof into two steps corresponding to the two steps of your algorithm.

For the first inequality: First, $x_{n+1}<y_n$ from the first step (since $x_n\lt y_n$); then, $y_{n+1}>x_{n+1}$ from the second step (since $y_n>x_{n+1}$).

For the second inequality: First, the distance is halved in the first step, i.e. $y_n-x_{n+1}=(y_n-x_n)/2$. Then, the distance is more than halved in the second step, that is, $y_{n+1}-x_{n+1}<(y_n-x_{n+1})/2=(y_n-x_n)/4$, due to the arithmetic/geometric mean inequality.

[Edit:] About the limits: Yes, this too can be shown. The $x_n$ are bounded from above (e.g. by $y_0$), and the $y_n$ are bounded from below by (e.g. by $x_0$). Also, $$x_{n+1}=(x_n+y_n)/2>(x_n+x_n)/2=x_n$$ and $$y_{n+1}=\sqrt{x_{n+1}y_n}<\sqrt{y_ny_n}=y_n\;,$$ so both sequences are monotonic. It follows that they both converge. Then since the difference converges to $0$, the limits must coincide.

-