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 ?
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.
