# Limit of recurrence sequence

I have to find a limit (or prove it doesn't exist) for the following recurrence sequence.

$a_1 = 2; a_{n+1} = \frac{1}{2}(a_n + \frac{2}{a_n})$

Now I know, in order to find the limit, I first need to prove that the sequence is monotonic and bounded. I've made a partial table of values and concluded that the sequence is decreasing, thus to prove monotonicity, I've written down:

$a_{n+1} < a_n \rightarrow a_n > \sqrt{2}$

And that's all I could think of. I don't think the inequality above proves anything so I don't know how to continue. I tried to calculate limit of the sequence by using limits of elements as follows:

$\lim a_{n+1} = \frac{1}{2}(\lim a_n + \lim \frac{2}{a_n}) = a\Rightarrow a = \sqrt{2}$

But without proving monotonicity and bounding, there's no proof the limit exists at all.

Thank you for any help in advance.

• You may try to prove that $\{a_n\}_{n\geq 1}$ is decreasing and bounded below by $\sqrt{2}$ (hence convergent to some limit $L$ fulfilling $L=\frac{1}{2}\left(L+\frac{2}{L}\right)$). This is the Babylonian algorithm / Newton's method for finding $\sqrt{2}$. – Jack D'Aurizio Dec 26 '17 at 17:09
• Solve the inequalities $\frac{1}{2}(a_n+\frac{2}{a_n})>a_n$ and $\frac{1}{2}(a_n+\frac{2}{a_n})>\sqrt{2}$. What you already have shown : If a limit exists, it must be $\sqrt{2}$ – Peter Dec 26 '17 at 17:10
• Sometimes, it is also called the Heron-method. – Peter Dec 26 '17 at 17:12

## 3 Answers

That is the Babylon's algorithm use to extract the root of a real number, hence the limit you found is good. Have you seen how to study sequences of the form $a_{n+1}=f\left(a_n\right)$ ? You can also focus on $\displaystyle \frac{a_{n+1}}{a_n}$ since the sequence is never null.

one prove easy that $$a_n>0$$ for all $n$ then we have by $AM-GM$ $$a_{n+1}=\frac{1}{2}\left(a_n+\frac{2}{a_n}\right)\geq \sqrt{a_n\cdot \frac{2}{a_n}}=\sqrt{2}$$

Let's follow the induction hypothesis that $a_{n}$ is decreasing. We know it's true for $n=1$ and $n=2$. And we have $$a_{n+1}-a_{n} = \frac{1}{2}\left(a_{n}-a_{n-1} \right) - \frac{a_{n-1}-a_{n}}{a_{n}a_{n-1}} > 0$$ Since $a_{n}a_{n-1} - 2 > 0$ as it has the same sign as $a_{n-1}^2-2$, and we have $a_{n-1}^2 = \frac{1}{2} (a_{n-2}+\frac{2}{a_{n-2}}) \geq \sqrt{2}$, by AM-GM.