Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
add comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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