6
$\begingroup$

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

  • 0
    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})$](http://math.stackexchange.com/questions/82682/proof-of-convergence-babylonian-method-x-n1-frac12x-n-fracax-n)2012-11-03

3 Answers 3

6

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

  • 0
    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$. ;)2012-11-03
4

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

3

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

  • 0
    Of course, AM-GM would have been a handy tool. Thanks!2012-11-03