# Cauchy sequence & Convergence

1. Feb 9, 2010

### kingwinner

1. The problem statement, all variables and given/known data
Least Upper Bound (LUB) Principle: every nonempty subset S of R that is bounded above has a least upper bound.
Completeness Theorem: every Cauchy sequence of real numbers converges. So R is complete.

To prove that Completness Theorem implies the least upper bound property (i.e. take the copmleteness theorem as an axiom, and use it to prove the LUB principle), my textbook suggests the following:
"Begin with any a1 in S and let b1 be an upper bound of S.
Let I1 = [a1,b1] . Let c be the midpoint of I1 . If c is an upper bound of S, let I2 be the first half of I1, otherwise let I2 be the second half. Repeat the process to get a nested sequence In = [an,bn] , the interested reader can verify that:
(i) (an) and (bn) are Cauchy sequences with a common limit L
(ii) and that L = sup S.
"

2. Relevant equations
N/A

3. The attempt at a solution
I'm struggling to prove (i).

1) By definition, an is Cauchy iff for all ε>0, there exists N s.t. if n,m≥N, then |an-am|<ε.
But I have no idea how to prove that (an) and (bn) in our problem are Cauchy. Can someone help me, please?

2) [solved] Now if we have proved that both an and bn converge, why does it follow that they must converge to a COMMON limit L? I can see that the legnth of the interval = bn-an ->0 as n->∞, so it's intuitvely believable that they both converge to a common limit, but how can we actually PROVE rigorously?

Thanks for any help!

Last edited: Feb 9, 2010
2. Feb 9, 2010

### ystael

Given $$[a_{n-1}, b_{n-1}]$$, there are only two possibilities for $$a_n$$. What are they? In each case, what is $$|a_n - a_{n-1}|$$? What does this tell you about $$|a_n - a_m|$$ for $$m > n$$?

For the second part, if the sequences $$(a_n)$$ and $$(b_n)$$ converge to $$A$$ and $$B$$ respectively, and $$b_n - a_n \to 0$$ as you say, what is $$B - A$$?

3. Feb 9, 2010

### kingwinner

1) The two possibilities: either an=an-1 or an=(an-1+bn-1)/2.
Definition: an is contractive iff there exists c<1 s.t. |an-an+1| ≤ c |an-1-an| for all n≥2.

Are you trying to suggest that we should prove that an is contractive? (since any contractive sequence is Cauchy)

For example, if we can show that |an-an+1| ≤ (1/2) |an-1-an| for all n≥2, then this implies (an) is Cauchy and we're done.
But I'm facing a problem. In our setting, it's possible that a1=a2, but a3>a2 in which case it will not be contractive?

2) Is the following a correct way to prove that they converge to a common limit?
Suppose lim an=A, lim bn=B. Then lim(an-bn)=lim(an)-lim(bn)=A-B, but we know lim(an-bn)=0, so by uniqueness of limit, A-B=0, and hence A=B.

Thanks for any help!

4. Feb 9, 2010

### ystael

(2) is correct.

For (1), in the case that $$a_3 > a_2 = a_1$$, what is the size of $$|a_3 - a_2|$$? How does it compare to the possible (not actual) size of $$|a_2 - a_1|$$? Don't use the definition of "contractive" literally; try to come up with something related that will do what you want.

5. Feb 10, 2010

### kingwinner

1)
For the case $$a_3 > a_2 = a_1$$,

$$|a_3-a_2|=(1/4)(b_1-a_1)$$

$$|a_2 - a_1|=0$$
So in this case, (an) is NOT contractive, and I'm in trouble...
Then how can we prove that (an) is Cauchy?

Could someone kindly explain a little more, please? (I know the definition of Cauchy, but I am not too sure how to actually do proofs with it. I've always been struggling to prove that something is Cauchy, and it's one of my biggest weaknesses and frustrations so far...)

6. Feb 10, 2010

### kingwinner

OK, so now I see that |an+1-an|≤(1/2n-1)(b1-a1). With this, how can we prove an is Cauchy?

But in the definition of Cauchy, we have |an-am|. What should we do? (I'm always confused when I get to this step when proving something is Cauchy...I just don't know what to do...)

Thank you!!

7. Feb 10, 2010

### Mandark

Suppose $$m,n\ge N$$ with $$n > m$$. We need to show that $$|a_n - a_m|$$ is small when N is large, can you find an upperbound for this using the bound you wrote in your last post (i.e. an upperbound on $$|a_{i+1} - a_i|$$), together with the triangle inequality?

8. Feb 10, 2010

### kingwinner

WHY can we assume n>m in the first place???

If n>m,
|an - am|
≤|an-an-1|+|an-1-an-2|+...+|am+1-am|
≤(1/2n-2)(b1-a1)+(1/2n-3)(b1-a1)+...+(1/2m-1)(b1-a1)
But still I'm stuck...how can we prove that it is Cauchy??

Thanks!

9. Feb 10, 2010

### Mandark

Well if m = n, then an upperbound is 0. If m > n, then you can switch m and n without loss of generality.

Now factor $$(b_1 - a_1)$$ out of the last expression, and sum the geometric sum. Then try to bound the result by something that involves N, which will allow you to show that you can make the initial expression as small as you like by making N large enough.

10. Feb 10, 2010

### kingwinner

What do you mean by without loss of generality?

Should I sum the finite geoemtric series or infinite geometric series?
If it's the finite geoemtric series, then the expression will depend on BOTH n and m, what should I do? And how can I find N?

Thank you!

11. Feb 10, 2010

### Mandark

Either should work. The entire infinite geometric series is still an upperbound. That deals with n, now to deal with m make use of the fact that $$m \ge N$$ to find an upperbound for the resulting expression in terms of N only.

12. Feb 10, 2010

### kingwinner

If n>m,
|an - am|
≤|an-an-1|+|an-1-an-2|+...+|am+1-am|
≤(1/2n-2)(b1-a1)+(1/2n-3)(b1-a1)+...+(1/2m-1)(b1-a1)
=(b1-a1)(1/2n-2+1/2n-3+...+1/2m-1)
<(b1-a1)(1/2m-1+1/2m+...)
=(b1-a1)(1/2m-1)(1+ 1/2+...)
=(b1-a1)(1/2m-1)[1/(1-1/2)]
=(b1-a1)(1/2m-2)
But I don't see how to find N s.t. if n,m≥N, then |a_n-a_m|<ε.

thanks for any help.