Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Okay, I'm really sick and tired of this problem. Have been at it for an hour now and we all know the drill: if you don't get to the solution of a simple problem, you won't, so ...

I'm working on a proof for the convergence of the Babylonian method for computing square roots. As a warming up I'm first using the sequence $(x_n)$ defined by:

$$ x_1 = 2\\ x_{n+1} = \frac{1}{2} (x_n + \frac{2}{x_n}) $$

Now for the proof, I want to show that: $\forall n \in \mathbb{N}: x^2_n > 2$. I want to prove this using induction, so this eventually comes down to:

$$ x_n^2 > 2 \implies x_{n+1}^2 = \frac{1}{4}x_n^2 + 1 + \frac{1}{x_n^2} > 2 $$

And I can't seem to get to the solution. Note that I don't want to make use of showing that $x=2$ is a minimum for this function using derivatives. I purely want to work with the inequalities provided. I'm probably seeing through something very obvious, so I would like to ask if anyone here sees what's the catch.

Sincerely, Eric

share|improve this question
    
In relation to the problem you are working on - this question might be useful: Proof of Convergence: Babylonian Method $x_{n+1}=\frac{1}{2}(x_n + \frac{a}{x_n})$ –  Martin Sleziak Nov 3 '12 at 14:39

3 Answers 3

First, swap $x_n^2$ for $2y$, just to make it simpler to write. The hypothesis is then $y > 1$, and what we want to show is $$ \frac{2}{4}y + \frac{1}{2y} > 1 $$ $$ y + \frac{1}{y} > 2 $$ Multiply by $y$ (since $y$ is positive, no problems arise) $$ y^2 -2y + 1 > 0 $$ $$ (y-1)^2 > 0 $$ which is obvious, since $y > 1$.

share|improve this answer
    
Of course, showing that the sequence is strictly decreasing and bounded below by $\sqrt{2}$ is not the same as showing that it in fact converges to it. –  Arthur Nov 3 '12 at 14:04
    
Thank you so much! You know that feeling when you know it's a really simple problem and you just can't see it? Frustration raged. ;) –  Eric Spreen Nov 3 '12 at 14:11
1  
@EricSpreen I know that feeling very well. The feeling those few times when you actually DO discover a really simple solution after a long time of staring at the problem is the reason I love mathematics. To get there, you need to be stuck first. –  Arthur Nov 3 '12 at 14:17
    
By the way, I'm planning on showing now that $x_n - x_{n+1} \geq 0$, so that is indeed monotone and bounded and then using limit algebra: writing $\lambda = \lim_{n \to \infty} x_n$: $\lambda = (\lambda + 1/\lambda)/2 \implies \lambda^2 = 2 \implies \lambda = 2$. ;) –  Eric Spreen Nov 3 '12 at 14:23

Write $$x_{n+1}^2 -2 = \left(\frac{1}{2} \left(x_n+\frac{2}{x_n}\right)\right) ^2 -2 = \frac{x_n^2}{4}+\frac{1}{x_n^2} -1 =\left( \frac{x_n}{2} - \frac{1}{x_n}\right)^2 \ge 0 $$ as any number squared is positive. This shows that $x_n^2 \ge 2$ for all choices of $n$.

share|improve this answer
1  
+1 An answer just in one line. :) –  B. S. Nov 21 '12 at 17:09

Just in case you don't insist on using induction.

$$\left(x+\frac2x\right)^2 \ge 8 \Leftrightarrow x^2+4+\frac4{x^2} \ge 8 \Leftrightarrow x^2-4+\frac4{x^2}\ge 0 \Leftrightarrow \left(x-\frac2x\right)^2\ge 0$$ The equality holds if and only if $x-\frac2x=0$, i.e. if $x^2=2$.

This is very similar to the usual derivation of AM-GM inequality for two variables.

(Or you could use directly AM-GM, if you are familiar with it.)

share|improve this answer
    
Of course, AM-GM would have been a handy tool. Thanks! –  Eric Spreen Nov 3 '12 at 14:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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