Proving (i) for Cauchy Sequences in Completeness Theorem

[kingwinner]

Homework Statement

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 I₁ = [a₁,b₁] . Let c be the midpoint of I₁ . If c is an upper bound of S, let I₂ be the first half of I₁, otherwise let I₂ be the second half. Repeat the process to get a nested sequence I_n = [a_n,b_n] , the interested reader can verify that:
(i) (a_n) and (b_n) are Cauchy sequences with a common limit L
(ii) and that L = sup S. "

Homework Equations

N/A

The Attempt at a Solution

I'm struggling to prove (i).

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

2) [solved] Now if we have proved that both a_n and b_n converge, why does it follow that they must converge to a COMMON limit L? I can see that the legnth of the interval = b_n-a_n ->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!

 

[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$$?

 

[kingwinner]

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

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

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

For example, if we can show that |a_n-a_n+1| ≤ (1/2) |a_n-1-a_n| for all n≥2, then this implies (a_n) is Cauchy and we're done.
But I'm facing a problem. In our setting, it's possible that a₁=a₂, but a₃>a₂ 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!

 

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

 

[kingwinner]

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

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, (a_n) is NOT contractive, and I'm in trouble...
Then how can we prove that (a_n) 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...)

 

[kingwinner]

OK, so now I see that |a_n+1-a_n|≤(1/2^n-1)(b₁-a₁). With this, how can we prove a_n is Cauchy?

But in the definition of Cauchy, we have |a_n-a_m|. 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!

 

[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?

 

[kingwinner]

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?

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

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

Thanks!

 

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

 

[kingwinner]

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.

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!

 

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

 

[kingwinner]

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.

If n>m,
|a_n - a_m|
≤|a_n-a_n-1|+|a_n-1-a_n-2|+...+|a_m+1-a_m|
≤(1/2^n-2)(b1-a1)+(1/2^n-3)(b1-a1)+...+(1/2^m-1)(b1-a1)
=(b1-a1)(1/2^n-2+1/2^n-3+...+1/2^m-1)
<(b1-a1)(1/2^m-1+1/2^m+...)
=(b1-a1)(1/2^m-1)(1+ 1/2+...)
=(b1-a1)(1/2^m-1)[1/(1-1/2)]
=(b1-a1)(1/2^m-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.