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
Best Answer
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}$.