monotone sequence theorem

The Monotone Sequence Theorem says that all monotonic sequences which are bounded will converge and the limit is their least upper bound or greatest lower bound (depending on the direction of the sequence).

In layman's terms this means that if you have a series of numbers which always gets bigger of small (thats what monotonic means) e.g. 1,1/2,1/3,1/4,... and you know that they never exceed a certain number, e.g. in this case they never get less that 0, or -1, or -2, ...). Then if you keep on down the sequence you will eventually (in a mathematical sense) reach a limit and this limit is the smallest number the sequence is bigger than, (or biggest number the sequence is smaller than if the sequence is decreasing).

Another two variant theorems which can also go by the name "monotone sequence theorems" are this pair, which allow us to find monotone subsequences in every sequence.

1. THEOREM. Let a₁,a₂,... be an infinite sequence of real numbers. Then there exists an infinite subsequence a_k1,a_k2,... (with k₁<k₂<...) which is (weakly) monotone.
2. THEOREM. Let a₁,...,a_mn+1 be a finite sequence of real numbers. Then either there exists a weakly ascending subsequence a_j1≤...≤a_jm+1 (with j₁<...<j_m+1), OR there exists a weakly descending subsequence a_k1≥...≥a_kn+1 (with k₁<...<k_n+1).

Using the first theorem, together with Gaff's theorem above, immediately proves the Heine-Borel theorem and the Bolzano-Weierstrass theorem (really both the same). The second theorem is a little-known elementary exercise.

The amazing thing about these is not their difficulty but the fact that concrete conclusions can be drawn from what looks to be no information at all! It is also interesting to contemplate how the second theorem, which is somewhat more difficult to prove than the first, is a "finite version" of the first.

Proofs

The proofs of both theorems work by assuming no desired subsequence in one direction exists (say, there is no ascending subsequence as desired), and drawing a conclusion that a desired subsequence in the other direction must therefore exist. Both are elementary (in the sense of requiring no knowledge beyond high school mathematics, not in the sense of being easy!): since nothing is really known about the sequences, none of the high-powered tools of mathematics can blast away the problem, and we're forced to work. Both make good exercises, so you may care to try to prove them yourself before continuing to the proofs.

1. monotone sequence theorem (infinite version) proof
2. monotone sequence theorem (finite version) proof