# Limit of recursive sequence $a_n=\frac{(x/a_{n-1})+a_{n-1}}{2}$

Let $x$ and $y$ be positive numbers. Let $a_0=y$, and let $$a_n=\frac{(x/a_{n-1})+a_{n-1}}{2}$$Prove that the sequence $\{a_n\}$ has limit $\sqrt{x}$.

I rearranged the equation to be $a_n-\sqrt{x}=\dfrac{(a_{n-1}-\sqrt{x})^2}{2a_{n-1}}$. I think I should try to bound $a_n-\sqrt{x}$ to be close to $0$, but I don't know how I should take care of the $2a_{n-1}$ term in the denominator.

• Hint: If the sequence converges (you'll have to prove that) then $\lim_{n\to\infty}a_n-a_{n-1}=0$, since all convergent sequences are Cauchy. Equivalently, $\lim_{n\to\infty}a_n=\lim_{n\to\infty}a_{n-1}=\ell$, so you can substitute $\ell$ for both $a_n$ and $a_{n-1}$ if you can show $\{a_n\}$ converges.
– Zen
Jun 9 '13 at 2:56
• Ok, I can prove that $a_1,a_2,a_3,\ldots$ is decreasing with lower bound $\sqrt{x}$, so it should converge. Then Zen's hint finishes the problem. Jun 9 '13 at 3:08
• In fact, I recommend you write it as an answer to your own question and accept it. Jun 9 '13 at 3:09

Note that for $n\geq 1$, we have $a_n<a_{n-1}$ iff $a_{n-1}>\sqrt{x}$ (simple manipulation from the given recurrence.)
Also, $a_1,a_2,a_3,\ldots >\sqrt{x}$. (Complete the squares from the given recurrence.) So $a_1,a_2,a_3,\ldots$ is decreasing. Since the sequence is decreasing with lower bound, it must converge.
Suppose its limit is $L$. Then $L = \dfrac{x/L+L}{2}$, implying $L=\sqrt{x}$.