Prove upper bound for recurrence

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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 $$

Answer 5

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