The Invariance Principle

Question

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.

Answer 1

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

Answer 2

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.