0
$\begingroup$

Possible Duplicate:
Proof of Convergence: Babylonian Method $x_{n+1}=\frac{1}{2}(x_n + \frac{a}{x_n})$

Let $(x_{n})$ be a sequence of rational numbers defined recursively : $x_0=1$, $x_{n+1}=\frac{1}{2}(x_{n}+\frac{2}{x_{n}})$.
Prove that that sequence is Cauchy without using any form of the Completeness property

  • 1
    @Donkey_2009: Genetic experiment gone wrong; Chernobyl Apples; "Feed me, Seymour!".2012-04-02

3 Answers 3

0

We're not allowed to use the Completeness Axiom, so we're going to have to formulate the proof so that all terms involved are rational. So I'm going to start by showing that $x_n^2\to 2$.

$x_{n+1}^2=\left (\frac{1}{2}\left (x_n+\frac{2}{x_n}\right )\right )^2=\frac{1}{4}\left (x_n^2+\frac{4}{x_n^2}+4\right )=\frac{x_n^2}{4}+\frac{1}{x_n^2}+1$

We now rewrite $x_n^2$ as $2(1+\delta_n)$ and get:

$ \begin{align} 2(1+\delta_{n+1}) &=\frac{1+\delta_n}{2}+\frac{1}{2(1+\delta_n)}+1\\ &=\frac{1}{2}+\frac{\delta_n}{2}+\frac{1}{2}-\frac{\delta_n}{2(1+\delta_n)}+1\\ &=2+\frac{\delta_n^2}{2(1+\delta_n)}\\ \end{align} $

So,

$\delta_{n+1}=\frac{\delta_n^2}{4(1+\delta_n)}$

Now in all of this I've assumed that $\delta_n \neq -1$, whereas $\delta_0$ is in fact $-1$. This doesn't matter: we'll start from $\delta_1$, and it should be fairly clear that $\delta_n$ is positive for all $n\ge 1$.

$x_1^2=\frac{1}{4}+1+1=2\left (1+\frac{1}{8}\right )\textrm{ so }\delta_1=\frac{1}{8}$

Now for simplicity's sake we note that $0<\delta_n<1$ for all $n\ge 1$, so

$\delta_{n+1}=\frac{\delta_n^2}{4(1+\delta_n)}<\frac{\delta_n}{4}.$

Now $\delta_1=\frac{1}{8}$, so it is obvious that $\delta_n<\frac{1}{2}\times\left (\frac{1}{4}\right )^n$ for all $n\ge 1$ (though you can come up with a formal proof using induction, if you like). This sequence clearly tends to $0$ (and you can prove that using the definition of convergence if you like). Therefore, $x_n^2=2(1+\delta_n)\to 2(1+0)=2$.

Now we know that $x_n>0$ for all $n\ge 1$, and we (I hope) know the result that for convergent sequences $a_n\to a$ and $b_n\to b$, $a_n\times b_n\to a\times b$.

Now suppose that $(x_n)$ diverges. But then $(x_n^2)$ also diverges, which is a contradiction. So $(x_n)$ converges to a limit, which we shall call $x$. Now $x_n^2\to x^2$, so $x^2=2$. Clearly $x$ is positive, so $x=\sqrt{2}$.

I see no reason to use any form of the Completeness Axiom for the Real Numbers. This proof of the statement holds in the algebraic numbers and $\mathbb{Q}\cup \{\sqrt{2}\}$ as well as in the reals, whereas the Completeness Axiom only holds in the Real Numbers, so using it weakens the proof.

  • 0
    No - we both proved that $x_n^2\to 2$, but that does not imply that $x_n\to \sqrt{2}$ or that $(x_n)$ is a Cauchy sequence. For example, if we were working over the rational numbers rather than the real numbers (which we might as well be doing since we're not allowed to use completeness), $x_n^2$ would still tend to $2$, but $x_n$ would not converge, as for any $x$ in $\mathbb{Q}$ we can find some $\varepsilon$ such that for all $N$ there is some n>N with $|x_n-x|\ge \varepsilon$ - just take $\varepsilon$ to be some rational number less than $|x-\sqrt{2}|$.2012-04-01
4

For $x_n>0$,


$ x_{n+1}=\frac12\left(x_n+\frac{2}{x_n}\right)=\frac12\left(\sqrt{x_n}-\sqrt{\frac{2}{x_n}}\right)^2+\sqrt{2}\ge\sqrt{2}\tag{1} $
Edit: a good point was raised regarding the existence of the square roots above. Instead, we can use $ x_{n+1}^2=\frac14\left(x_n+\frac{2}{x_n}\right)^2=\frac14\left(x_n-\frac{2}{x_n}\right)^2+2\ge2\tag{1} $ Thus, each $x_n$ after the first must satisfy $x_n^2\ge2$. This implies $ x_{n+1}-x_n=\frac{2-x_n^2}{2x_n}\le0\tag{2} $ Since $\{x_n\}$ is a decreasing sequence, bounded below, it is a Cauchy sequence.

Moved to this answer, which required extra work. This seems to indicate that the questions are not equivalent.

  • 1
    @Donkey_2009: Thanks again. $\sqrt{x_n}$ also poses a problem. I think the repaired equation $(1)$ above removes all assumptions about the Completeness Property.2012-04-02
2

You might wish to show recursively that, for every $n\geqslant0$, $1\leqslant x_n\leqslant3/2$ and $ x_{n+1}^2-2=\frac{(x_n^2-2)^2}{4x_n^2}\quad\text{hence}\quad 0\leqslant x_{n+1}^2-2\leqslant\frac14(x_n^2-2)^2 . $ This proves that, for every $n\geqslant1$, $2\leqslant x_n^2\leqslant2+1/4^{n}$, which implies the result you are after. (Naturally, the rate of convergence is much faster but this control seems to be sufficient for your purpose.)

  • 0
    Thanks, that is what I wanted2012-04-01