This question already has an answer here:

Define the sequence of numbers $A_i$ by

$$A_0 = 2$$

$$A_{n+1} = \frac{A_n}{2} + \frac{1}{A_n} \quad \text{for} \ n \geq 1$$

Prove that $$ A_n \leq \sqrt{2} + \big(\frac{1}{2}\big)^n \quad \forall n \geq 0. $$ I already tried induction but it didn't help in this case.

The question is : beside induction what is other approach to solve this kind of problem ?


marked as duplicate by Martin R, Sil, Namaste, Error 404, José Carlos Santos Oct 27 '17 at 18:25

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Could you please refer to Mathjax help and edit your question? $\endgroup$ – Ivon Oct 26 '17 at 9:15
  • $\begingroup$ Hint: You have $$A_{n+1}-\sqrt{2}=\frac{(A_n-\sqrt{2})^2}{2A_n}$$ $\endgroup$ – Kelenner Oct 26 '17 at 9:26
  • $\begingroup$ @Kelenner what does this equation mean ? It means Ai alway greater than √2 and this will help me with induction or there is another approach ? $\endgroup$ – xuoimai Oct 26 '17 at 9:53
  • $\begingroup$ Also: math.stackexchange.com/q/2186571/42969 – found instantly using Approach0 $\endgroup$ – Martin R Oct 26 '17 at 11:07

If you rewrite $$A_{n+1} = \frac{A_n}{2} + \frac{1}{A_n} $$ as $$A_{n+1} =A_n-\frac{A_n}{2} + \frac{1}{A_n}=A_n-\frac{A_n^2-2}{2A_n} $$ you probably recognize Newton iterative scheme for solving $A^2-2=0$ starting with a guess $A_0$.


Since the definition is recursive, induction is natural for this problem, and it works if you first show $A_n \ge \sqrt{2}$, for all $n$.

Based on that strategy, here's a proof . . .

If $A_n\;$is positive, so is $A_{n+1},\;$hence, since $A_0 = 2 > 0,\;$it follows that $A_n > 0,\;$for all $n$.

Note that $A_0 = 2 > \sqrt{2}$.

By AM-GM, $$A_{n+1} = \frac{A_n}{2} + \frac{1}{A_n} \ge 2\sqrt{\frac{1}{2}} = \sqrt{2}$$ Thus, $A_n \ge \sqrt{2},\;$for all $n$.

The goal is to prove $A_n \le \sqrt{2} + {\Large{\frac{1}{2^n}}},\;$for all $n$.

Proceed by induction on $n$.

For $n=0,\;$we have $A_0 = 2 < \sqrt{2} + 1 = \sqrt{2} + {\Large{\frac{1}{2^0}}}$.

Assume the inequality $A_n \le \sqrt{2} + {\Large{\frac{1}{2^n}}}\;$holds for some integer $n \ge 0$. \begin{align*} \text{Then}\;\;A_{n+1} &= \frac{A_n}{2} + \frac{1}{A_n}\\[4pt] &\le \frac {\sqrt{2} + {\Large{\frac{1}{2^n}}}}{2} + \frac{1}{\sqrt{2}}\\[4pt] &=\frac{\sqrt{2}}{2} + \frac{1}{2^{n+1}}+ \frac{\sqrt{2}}{2}\\[4pt] &=\sqrt{2} + \frac{1}{2^{n+1}}\\[4pt] \end{align*} which completes the induction, and thus completes the proof.


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