3
$\begingroup$

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

Upper bound and recurrence

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It didn't occur to me to prove that $A_n \ge \sqrt2$ and then substitute $\sqrt2$ in the $1/A_n$ term. Much easier that way. Thanks. $\endgroup$ – Bobby Durrett May 28 '16 at 2:36
  • 1
    $\begingroup$ @BobbyDurrett: You are welcome. The inequality $A_n\gt \sqrt{2}$ is not mentioned explicitly in what you are asked to show, but when one tries to push the induction through, it becomes clear that it is necessary for the proof. $\endgroup$ – André Nicolas May 28 '16 at 2:40
  • $\begingroup$ Nice induction for the $>\sqrt{2}$ part. I didn't manage it immediately, that's why I showed it studying the map $x\mapsto \frac{x}2+\frac{1}{x}$. $\endgroup$ – Daniel Robert-Nicoud May 28 '16 at 11:09
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.