Prove upper bound for recurrence I am working on problem set 8 problem 3 from MIT's Fall 2010 OCW class 6.042J. This is covered in chapter 10 which is about recurrences.
Here is the problem:
$$A_0 = 2$$
$$A_{n+1} = A_n/2 + 1/A_n, \forall n \ge 1$$
Prove 
$$A_n \le \sqrt2 + 1/2^n,  \forall n \ge 0$$
I have graphed the recurrence and the upper bound and they seem to both converge on $\sqrt2$.

Also, if you ignore the boundary condition $A_0 = 2$ then you find that $\sqrt2$ is a solution to the main part of the recurrence. i.e. $\sqrt2 = \sqrt2/2 + 1/\sqrt2$.
The chapter and videos on recurrences have a lot to say about a kind of cookbook solution to divide and conquer recurrences which they call the Akra-Bazzi Theorem. But this recurrence does not seem to be in the right form for that theorem. If it were in the form $A_{n+1} = A_n/2 + g(n)$ then the theorem would give you an asymptotic bound. But $1/A_n$ is not a simple function of $n$ like a polynomial. Instead it is part of the recurrence.
Also, the chapter has a variety of things to say about how to guess the right solution and plug it into an inductive proof, but I haven't had much success. I have tried possible solutions of various forms like $a_n = \sqrt2+a/b^n$ and tried solving for the constants $a$ and $b$ but to no avail.
So, if someone can point me in the right direction that would be great. I always assume that the problem sets are based on something taught in the videos and in the text of the book but I am having trouble tracking this one down.
Bobby
 A: We show by induction that
$$\sqrt{2}\lt A_n\le \sqrt{2}+\frac{1}{2^n}.\tag{1}$$
Suppose the result holds at $n=k$. We show the result holds at $n=k+1$. 
For the inequality on the right of (1), we need to show that
$$\frac{A_k}{2}+\frac{1}{A_k}\le \sqrt{2}+\frac{1}{2^{k+1}}.$$
By the induction hypothesis, we have
$$\frac{A_k}{2}+\frac{1}{A_k}\le \frac{\sqrt{2}}{2}+\frac{1}{2^{k+1}}+\frac{1}{\sqrt{2}}=\sqrt{2}+\frac{1}{2^{k+1}},$$
which takes care of the induction step for the inequality on the right of (1).
We still need to show that $\sqrt{2}\lt A_{k+1}$. Let $A_k=\sqrt{2}+\epsilon$, where $\epsilon$ is positive. Then
$$A_{k+1}=\frac{\sqrt{2}+\epsilon}{2}+\frac{1}{\sqrt{2}+\epsilon}=\frac{4+2\sqrt{2}\epsilon+\epsilon^2}{2(\sqrt{2}+\epsilon)}\gt \frac{4+2\sqrt{2}\epsilon}{2(\sqrt{2}+\epsilon)}=\sqrt{2}.$$
This completes the induction step for the inequality on the left of (1).
Remark: The inequality (1) and squeezing show that $A_n$ indeed has limit $\sqrt{2}$.
A: Let $$B_k = \frac{A_k}{\sqrt{2}}$$
Then $B_0 = \sqrt{2}$ and 
$$
B_{n+1} = \frac12\left(B_n+\frac{1}{B_n} \right)
$$
Thus $b_n$ is the $n$-th guess if you perform Newton's algorithm to try to find $\sqrt{1}$ starting with a guess of $\sqrt{2}$.
This recursion can be solved in closed form using the formula for the hyperbolic tangent of $2x$ in terms of $\tanh x$:
$$\tanh(2x) = \frac{2 \tanh x}{1+\tanh^2{x}}$$
.  The result looks something like 
$$B_n = \tanh\left( 2^n \theta\right)
$$  where $\theta = \tanh^{-1} B_0$; the answer I have given is off in that  every other term needs to be the reciprocal of what I wrote, but the general idea will work.  
Once you have that, you can know exactly what $B_n$ is and prove the relation; or better yet, use the error analysis for Newton's method to get an estimate of how close to 1 you would be.
A: We want to apply induction, but we need also a lower bound on $A_n$ for the $\frac{1}{n}$ term. We can show that $A_n\ge\sqrt{2}$ as follows:
Let $f(x) = \frac{x}{2} + \frac{1}{x}$. Then $f'(x) = \frac{1}{2} - \frac{1}{x^2}$ which has a zero at $x = \sqrt{2}$ where $f(\sqrt{2}) = \sqrt{2}$, and is positive for $x>\sqrt{2}$. This shows that $f(x)\ge\sqrt{2}$ whenever $x\ge\sqrt{2}$, and as $A_{n+1} = f(A_n)$, we have that $A_n\ge\sqrt{2}$ for all $n\ge0$.
Then to conclude:
The case $n=0$ is trivially true.
For $n\ge0$ we have that
$$A_{n+1} = \frac{A_n}{2} + \frac{1}{A_n}.$$
By induction hypothesis and what we have shown above, this has as upper bound
$$A_{n+1}\le \frac{\sqrt{2} + 2^{-n-1}}{2} + \frac{1}{\sqrt{2}} = \sqrt{2} + 2^{-n-1}.$$
A: Three steps: Use the definition of $A_n$ and algebra to establish that
$$
A_{n+1}-\sqrt 2 = {(A_n-\sqrt 2)^2\over 2A_n}.\tag1
$$
Next, use (1) to prove by induction that
$$
A_n\ge\sqrt 2\ \text{for every $n$.}\tag2$$
Finally, use (1) and (2) to prove by induction that
$$
A_n-\sqrt2 \le \frac1{2^{n}}\ \text{for every $n$.}\tag2
$$
A: Your sequence is
$$
A_{n+1} = \frac{1}{2} A_n + \frac{1}{A_n}
$$
where the last term features a division which reminds of the Newton-Raphson iteration.
Newton Raphson iteration takes the root of the tangent as next step for estimating a root of $f$:
$$
0 = T'(x_{n+1}) = f(x_n) + f'(x_n) (x_{n+1} - x_n) \iff \\
x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}
$$
by comparison we have
$$
-\frac{1}{2}A_n + \frac{1}{A_n} = - \frac{A_n^2-2}{2A_n} = - \frac{f(A_n)}{f'(A_n)}
$$
and see $f(x) = x^2 - 2$, the function used to iterate against the root $\sqrt{2}$.
