Next: 8. Continuity Up: 7. Complex Sequences Previous: 7.7 The Translation Theorem   Index

# 7.8 Bounded Monotonic Sequences

7.87   Theorem. Let be a binary search sequence in . Suppose where .Then is a null sequence. Also and .

Proof: We know that , and that is a null sequence, so is a null sequence. Since we know that for all , and hence

for all . By the comparison theorem for null sequences it follows that and are null sequences, and hence and

7.88   Definition (Increasing, decreasing, monotonic) Let be a real sequence. We say is increasing if for all , and we say is decreasing if for all . We say that is monotonic if either is increasing or is decreasing.

7.89   Theorem. Let be an increasing real sequence. Then for all

Proof: Define a proposition form on by

Then says for all '', so is true. Since is increasing, we have for all ,

By induction, we conclude that is true for all , i.e.

7.90   Corollary. Let be an increasing real sequence. Then for all ,
 (7.91)

Proof: For all

7.92   Definition (Upper bound, lower bound.) Let be a real sequence. We say that has an upper bound if there is a number such that for all . Any such number is called an upper bound for . We say that has a lower bound if there is a number such that for all . Any such number is called a lower bound for .

7.93   Examples. If for all then (or any number greater than ) is an upper bound for , and (or any number less than ) is a lower bound for . The sequence has no upper bound, but is a lower bound for .

7.94   Exercise. A In definition 7.41, we defined a complex sequence to bounded if there is a number such that for all . Show that a real sequence is bounded if and only if it has both an upper bound and a lower bound.

7.95   Theorem (Bounded monotonic sequences converge.)Let be
an increasing sequence in , and suppose has an upper bound. Then converges. (Similarly, decreasing sequences that have lower bounds converge.)

Proof: Let be an upper bound for . We will construct a binary search sequence satisfying the following two conditions:

i. For every , is an upper bound for ,

ii. For every , is not an upper bound for .

Let

A straightforward induction argument shows that satisfies conditions i) and ii).

Let be the number such that . I will show that .

We know that is a null sequence. Let be a precision function for , so that for all ,

I will use to construct a precision function for .

Let . Since is not an upper bound for , there is a number such that . By condition i), I know that for all . Hence, since is increasing, we have for all :

Since we also have

Hence

This says that is a precision function for , and hence

7.96   Corollary. Let be a real sequence. If has an upper bound, and there is some such that

then converges. Similarly, if has a lower bound, and there is some such that

then converges.

7.97   Example. Let . Define a sequence by

We have for all . Suppose converges to a limit . Since for all , we can use the translation theorem to show that

so , and hence , so must be . Since for all , it follows from the inequality theorem that , and hence if converges, it must converge to . In order to show that converges, it is sufficient to show that is decreasing. (We've already noted that is a lower bound.)

Well,

so if I can show that for all , then I'll know that is decreasing. Now

I also note that , so I finally conclude that is decreasing, and hence . In fact, this sequence converges very fast, and is the basis for the square root algorithm used on most computers.

7.98   Example ( ) We will show that

Claim: is a decreasing sequence.

Proof: For all ,

 (7.99)

We will show by induction that (7.99) holds for all . Let

Then says , which is true since . For all ,

By induction, is true for all , and the claim is proved.

Let Then , since any precision function for is also a precision function for . Hence

Thus , and hence . Since for all it follows from the inequality theorem that , and hence

7.100   Exercise. A Show that the sequence

is a null sequence.

7.101   Exercise. Criticize the following argument.

We know that .

Hence

7.102   Note.I got the idea of using precision functions from a letter by Jan Mycielski in the Notices of the American Mathematical Society[34, p 569]. Mycielski calls precision functions Skolem functions.

The snowflake was introduced by Helge von Koch(1870-1924) who published his results in 1906 [32]. Koch considered only the part of the boundary corresponding to the bottom third of our polygon, which he introduced as an example of a curve not having a tangent at any point.

The sequence from Exercise 7.82 is taken from [12, page 55, ex 20]

Next: 8. Continuity Up: 7. Complex Sequences Previous: 7.7 The Translation Theorem   Index