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.

  • $\begingroup$ 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. $\endgroup$
    – Zen
    Jun 9 '13 at 2:56
  • $\begingroup$ 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. $\endgroup$
    – PJ Miller
    Jun 9 '13 at 3:08
  • $\begingroup$ In fact, I recommend you write it as an answer to your own question and accept it. $\endgroup$
    – davidlowryduda
    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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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