# Math Help - Algorithm

1. ## Algorithm

Suppose we have

start: $(x_0, y_0)$ with $x_0 < y_0$.

step: $x_{n+1} = \frac{x_n+y_n}{2}$, $y_{n+1} = \sqrt{x_{n+1}y_n}$. Find $\lim x_n$ and $\lim y_n$.

So consider $\frac{x_{n+1}}{y_{n+1}} = \sqrt{\frac{1+ x_n/y_n}{2}}$. We know that $\cos \frac{\alpha}{2} = \sqrt{\frac{1- \cos \alpha}{2}}$. Put $\alpha_n = \frac{x_n}{y_n}$. Then $\cos \alpha_{n+1} = \cos \frac{\alpha_n}{2}$. Now how would we get $\alpha_n$? Because taking inverse cosines, we get $\alpha_{n+1} = \frac{\alpha_n}{2}$. So then $\alpha_{n} = \frac{\alpha_0}{2^n}$. Thus $2^n \arccos \frac{x^n}{y^n} = \arccos \frac{x_0}{y_0}$. From here, can we get the limit?

2. Originally Posted by Sampras
Suppose we have

start: $(x_0, y_0)$ with $x_0 < y_0$.

step: $x_{n+1} = \frac{x_n+y_n}{2}$, $y_{n+1} = \sqrt{x_{n+1}y_n}$. Find $\lim x_n$ and $\lim y_n$.

So consider $\frac{x_{n+1}}{y_{n+1}} = \sqrt{\frac{1+ x_n/y_n}{2}}$. We know that $\cos \frac{\alpha}{2} = \sqrt{\frac{1- \cos \alpha}{2}}$. Put $\alpha_n = \frac{x_n}{y_n}$. Then $\cos \alpha_{n+1} = \cos \frac{\alpha_n}{2}$. Now how would we get $\alpha_n$? Because taking inverse cosines, we get $\alpha_{n+1} = \frac{\alpha_n}{2}$. So then $\alpha_{n} = \frac{\alpha_0}{2^n}$. Thus $2^n \arccos \frac{x^n}{y^n} = \arccos \frac{x_0}{y_0}$. From here, can we get the limit?
No

You can show by induction that $(x_n)_n$ is increasing, $(y_n)_n$ is decreasing and $\forall n~x_n \leq y_n$

Starting from this you can show that $(x_n)_n$ has a limit since it is increasing and majored by $y_0$. The same for $(y_n)_n$.

Then you can show that $(x_n)_n$ and $(y_n)_n$ are adjacent since $x_{n+1}- y_{n+1} = \frac{x_n-y_n}{2\:\left(1+\sqrt{\frac{2y_n}{x_n+y_n}}\right) } \leq \frac{x_n-y_n}{4}$

Then you can show that $(x_n)_n$ and $(y_n)_n$ have the same limit l.

You can see that $2^n \arccos \frac{x_n}{y_n} = \arccos \frac{x_0}{y_0}$ may be true but $2^n$ has infinite limit whereas $\arccos \frac{x_n}{y_n}$ converges towards $\arccos 1 = 0$

3. Originally Posted by running-gag
No

You can show by induction that $(x_n)_n$ is increasing, $(y_n)_n$ is decreasing and $\forall n~x_n \leq y_n$

Starting from this you can show that $(x_n)_n$ has a limit since it is increasing and majored by $y_0$. The same for $(y_n)_n$.

Then you can show that $(x_n)_n$ and $(y_n)_n$ are adjacent since $x_{n+1}- y_{n+1} = \frac{x_n-y_n}{2\:\left(1+\sqrt{\frac{2y_n}{x_n+y_n}}\right) } \leq \frac{x_n-y_n}{4}$

Then you can show that $(x_n)_n$ and $(y_n)_n$ have the same limit l.

You can see that $2^n \arccos \frac{x_n}{y_n} = \arccos \frac{x_0}{y_0}$ may be true but $2^n$ has infinite limit whereas $\arccos \frac{x_n}{y_n}$ converges towards $\arccos 1 = 0$
And that limit would be $\frac{\sqrt{y_{0}^{2}-x_{0}^{2}}}{\arccos(x_0/y_0)}$ right?

4. Originally Posted by Sampras
And that limit would be $\frac{\sqrt{y_{0}^{2}-x_{0}^{2}}}{\arccos(x_0/y_0)}$ right?
Yes