# Proving recursive sequence converges to $\sqrt{2}$ [duplicate]

Consider the sequence $x_{n+1} = \frac{1}{2} (x_n + \frac{2}{x_n})$, $x_1 = 2$. Prove that it converges to $\sqrt{2}$.

I want to show that all of $x_n$ is bounded below by $\sqrt{2}$ using induction. However, I can't see how knowing $x_n \geq \sqrt{2}$ helps show that $\frac{1}{2} (x_n + \frac{2}{x_n}) \geq \sqrt{2}$. Namely, it's not clear whether a higher value of $x_n$ produces a lower (or higher) value of $x_{n+1}$.

Edit: I am looking for a solution that does not use AM-GM (which is proven later in the text that I am reading).

## marked as duplicate by choco_addicted, John B, Martin Sleziak, JMP, Community♦Apr 9 '16 at 7:19

• I believe your sequence is monotone decreasing...Sonnhard Grauber's suggestion to use AM-GM seems like a great approach... – User001 Apr 9 '16 at 5:31
• Show that if $x_n>\sqrt 2, \sqrt 2 <x_{n+1}<x_n$ – Doug M Apr 9 '16 at 5:36
• See also Proof of Convergence: Babylonian Method $x_{n+1}=\frac{1}{2}(x_n + \frac{a}{x_n})$ (and maybe other posts linked there.) – Martin Sleziak Apr 9 '16 at 6:45
• @SubhadeepDey You see the list in the linked questions in the sidebar, right? If there is too many of them to fit there, you can click on the link "see more linked questions..." The url has format as above. (You can test this basically on any question from the top of the list in the frequent tab.) – Martin Sleziak Apr 9 '16 at 6:54
• Thanks for the suggestions. I found this link most helpful: proofwiki.org/wiki/… – rorty Apr 9 '16 at 7:19

prove by induction that $$x_n>0$$ for all natural $$n$$ and then we get by AM-GM: $$x_{n+1}=\frac{1}{2}(x_n+\frac{1}{x_n})\geq\sqrt{2}$$
$1)$ $x_n > 0, \forall n \geq 1$.
$2)$ $x_{n+1} - 1 = \dfrac{x_n+\dfrac{2}{x_n}}{2}-1=\dfrac{(x_n-1)^2+1}{2x_n}> 0\Rightarrow x_n > 1, \forall n \geq 1$.
$3)$$0 \leq |x_{n+1} - \sqrt{2}| = \dfrac{|x_n-\sqrt{2}|^2}{2x_n}< \dfrac{|x_n-\sqrt{2}|^2}{2} \leq|x_n - \sqrt{2}|^2\Rightarrow |x_{n+1} -\sqrt{2}|< |x_1-\sqrt{2}|^{2^n}=|2-\sqrt{2}|^{2^n}$, and apply squeeze lemma to get the limit of $\sqrt{2}$ as claimed.