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.

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

share|improve this question

marked as duplicate by Aryabhata, t.b., Alex Becker, Asaf Karagila, Pedro Tamaroff Apr 2 '12 at 1:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
Why wouldn't you use the completeness property? –  Pedro Tamaroff Apr 1 '12 at 16:14
    
How exactly are we supposed to 'use' the Cauchy criterion? The only interesting thing about the Cauchy criterion is that any sequence satisfying the Cauchy criterion must converge, but this fact is equivalent to the Completeness Property of the Real Numbers. –  Donkey_2009 Apr 1 '12 at 16:15
    
3  
One answer to "Prove this sequence is Cauchy" is that some sequences are Cauchy sequences but no sequence is Cauchy. Cauchy was a person. I once met a mathematician who insisted on usages consistent with that position. –  Michael Hardy Apr 1 '12 at 17:18
1  
@Donkey_2009: Genetic experiment gone wrong; Chernobyl Apples; "Feed me, Seymour!". –  Asaf Karagila Apr 2 '12 at 15:33
show 8 more comments

3 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
Thanks, that is what I wanted –  Nameless Apr 1 '12 at 16:55
add comment

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.

share|improve this answer
    
'Since {xn} is a decreasing sequence, bounded below, is converges'. I think that counts as using a form of the Completeness Property. However, it is true that a decreasing sequence bounded below is always a Cauchy sequence, even over sets such as the rational numbers where the Completeness Property does not hold. –  Donkey_2009 Apr 1 '12 at 23:59
    
@Donkey_2009: thanks, I missed the part about not using the Completeness Property when I first answered. I have been gone until now, so I have just removed the claim of convergence. –  robjohn Apr 2 '12 at 0:09
    
Another slight issue - how do you know that $\sqrt{2}$ exists without invoking the Completeness Property for the Real Numbers? –  Donkey_2009 Apr 2 '12 at 20:01
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. –  robjohn Apr 2 '12 at 21:08
add comment

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.

share|improve this answer
    
A kind of big proof, when compared to Didier's one but thanks anyway. –  Nameless Apr 1 '12 at 17:09
    
..aaand the question has now changed completely. Since we've shown that $x_n\to \sqrt{2}$, we can now say that $|x_{n+1}-x_n|=|\frac{1}{x_n}-\frac{x_n}{2}|\to \frac{1}{\sqrt{2}}-\frac{\sqrt{2}}{2}=0$. So the sequence is Cauchy. And we didn't use the Completeness Axiom, but we went rather a long way round. –  Donkey_2009 Apr 1 '12 at 17:10
    
And I'm pretty sure that my proof is exactly equivalent to Dider's, which wasn't up when I started writing... :-( –  Donkey_2009 Apr 1 '12 at 17:11
    
I'm astonished that no one has noticed the contradiction in my post. I actually implicitly assumed completeness when I supposed that $x_n$ must either tend to a limit or diverge. Oh well.... –  Donkey_2009 Apr 1 '12 at 18:43
    
Well with Dieder's proof we have that $x_n^2\to 2$ and so that it is Cauchy (a Cauchy sequence if you prefer) and we have only used the fact that $\mathbb{R}$ is archimedean. –  Nameless Apr 1 '12 at 19:07
show 1 more comment

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