# Strong Induction on Recursive Sequence

I attempted to prove the following but am unsure if my logic is solid.

Define the sequence of numbers $A_i$, by
$A_0 = 2$

$A_{n+1} = \frac{A_n}{2} + \frac{1}{A_n}$ for $n\geq 1$
Prove that $A_n \leq\sqrt2 + \frac{1}{2^n}$ for all $n\geq0$.

proof attempt: (using strong induction)

assume $A_n$ is true for $A_0$, $A_1$, ... $A_n$,
prove $A_{n+1} \leq\sqrt2 + \frac{1}{2^{n+1}}$
substitute $A_n$ into recursive definition:
$A_{n+1} = \frac{\sqrt2 + \frac{1}{2^n}}{2} + \frac{1}{\sqrt2 + \frac{1}{2^n}}$

$\frac{\sqrt2 + \frac{1}{2^n}}{2} + \frac{1}{\sqrt2 + \frac{1}{2^n}} \leq \sqrt2 + \frac{1}{2^{n+1}}$
This is where I am unsure if my thinking is correct. I attempted to take the limit as n -> infinity such that all the 1/2^n terms go to 0.
We are left with...

$\frac{\sqrt{2}}{2} +\frac{1}{\sqrt2} \leq\sqrt2$
which gives

$\frac{2}{\sqrt2}\leq\sqrt2$,

which is true...but I am not sure if I just proved it for all n or just very large n.

Could somebody offer some feedback? Thank you.

• This is hard to read. Do you mean $A_{n+1}=\frac {A_n}2+\frac 1{A_n}$? – lulu Mar 14 '17 at 17:33
• Assuming you do, then Hint: it's easier to prove $\sqrt 2 ≤ A_n ≤ \sqrt 2 +\frac 1{2^n}$. – lulu Mar 14 '17 at 17:37
• yes lulu thank you – camdog Mar 14 '17 at 17:41
• Did that hint get the job done? I always like situations where it is easier to prove an apparently stronger statement. – lulu Mar 14 '17 at 17:43
• i am still not sure how to substitute that into the An+1 – camdog Mar 14 '17 at 17:46