Monotone sequences, subsequences and the Bolzano–Weierstrass theorem

Proving that a sequence converges from the definition requires knowing the limit in advance. Often we do not. This lesson gives the first of several theorems that guarantee convergence without naming the limit: a bounded monotone sequence converges. It is the sequence form of completeness, and it lets us define numbers such as \(e\) and \(\sqrt{2}\) as limits. We then study subsequences and prove the Bolzano–Weierstrass theorem, which says every bounded sequence has a convergent subsequence. This theorem is the workhorse behind the extreme value theorem and uniform continuity in lesson 9.

Monotone sequences

Definition. A sequence is increasing if \(a_n \le a_{n+1}\) for all \(n\), and decreasing if \(a_n \ge a_{n+1}\) for all \(n\). It is monotone if it is increasing or decreasing. (Some books say non-decreasing for what we call increasing, and strictly increasing when \(a_n < a_{n+1}\).)

Theorem (monotone convergence theorem). A monotone sequence converges if and only if it is bounded. An increasing bounded sequence converges to \(\sup \{a_n : n \in \mathbb{N}\}\), and a decreasing bounded sequence to \(\inf \{a_n\}\).

Proof. Convergent sequences are bounded (lesson 4). Conversely, let \((a_n)\) be increasing and bounded, and let \(s = \sup \{a_n\}\), which exists by completeness. Let \(\varepsilon > 0\). By the approximation property there is \(N\) with \(a_N > s - \varepsilon\). For \(n \ge N\), monotonicity gives \(a_n \ge a_N > s - \varepsilon\), and \(a_n \le s\) because \(s\) is an upper bound. So \(|a_n - s| < \varepsilon\) for \(n \ge N\), and \(a_n \to s\). The decreasing case follows by applying this to \((-a_n)\). \(\blacksquare\)

The theorem is equivalent to completeness. In \(\mathbb{Q}\), the truncations of \(\sqrt{2}\) form a bounded increasing sequence with no rational limit. So any proof of the monotone convergence theorem must use completeness, and ours used it in the form of the supremum.

Recursive sequences

The monotone convergence theorem is ideal for sequences defined by recursion, where a formula for \(a_n\) is not available.

The last step deserves a warning. Taking limits in a recursion only identifies the limit if we already know the limit exists. The recursion \(a_{n+1} = 2a_n\) with \(a_1 = 1\) satisfies \(L = 2L\) for \(L = 0\), but the sequence \(1, 2, 4, 8, \dots\) diverges.

Subsequences

Definition. Given a sequence \((a_n)\) and natural numbers \(n_1 < n_2 < n_3 < \dots\), the sequence \((a_{n_k})_{k \ge 1} = (a_{n_1}, a_{n_2}, a_{n_3}, \dots)\) is a subsequence of \((a_n)\).

A subsequence keeps infinitely many terms in their original order. For example, \(a_2, a_4, a_6, \dots\) and \(a_1, a_4, a_9, a_{16}, \dots\) are subsequences, but \(a_2, a_1, a_3, \dots\) is not. A simple induction shows that \(n_k \ge k\) for every \(k\).

Theorem. If \(a_n \to L\) then every subsequence also converges to \(L\).

Proof. Let \(\varepsilon > 0\) and choose \(N\) with \(|a_n - L| < \varepsilon\) for \(n \ge N\). If \(k \ge N\) then \(n_k \ge k \ge N\), so \(|a_{n_k} - L| < \varepsilon\). \(\blacksquare\)

This gives a quick test for divergence: if two subsequences converge to different limits, the sequence diverges. The sequence \((-1)^n\) has subsequences \(a_{2k} = 1\) and \(a_{2k-1} = -1\), so it diverges.

Every sequence has a monotone subsequence

The following combinatorial lemma is surprisingly powerful.

Lemma. Every sequence of real numbers has a monotone subsequence.

Proof. Call an index \(m\) a peak if \(a_m \ge a_n\) for every \(n > m\): the term \(a_m\) is at least as large as everything after it. There are two cases.

Case 1: there are infinitely many peaks \(m_1 < m_2 < \dots\). Then \(a_{m_1} \ge a_{m_2} \ge \dots\), since each peak is at least as large as every later term. This is a decreasing subsequence.

Case 2: there are finitely many peaks. Choose \(n_1\) larger than every peak. Since \(n_1\) is not a peak, there is \(n_2 > n_1\) with \(a_{n_2} > a_{n_1}\). Since \(n_2\) is not a peak either, there is \(n_3 > n_2\) with \(a_{n_3} > a_{n_2}\), and so on. This builds a strictly increasing subsequence. \(\blacksquare\)

The Bolzano–Weierstrass theorem

Theorem (Bolzano–Weierstrass). Every bounded sequence of real numbers has a convergent subsequence.

Proof. Let \((a_n)\) be bounded. By the lemma it has a monotone subsequence, which is bounded because the whole sequence is. By the monotone convergence theorem, this subsequence converges. \(\blacksquare\)

Bolzano proved a version of this in 1817 as part of his work on the intermediate value theorem; Weierstrass made it a central tool in his Berlin lectures from the 1860s. Here is a second proof that uses nested intervals and shows why the theorem is a statement about completeness.

Second proof. Suppose \(|a_n| \le M\) for all \(n\). Let \(I_1 = [-M, M]\), which contains every term. Split \(I_1\) into two closed halves. At least one half contains \(a_n\) for infinitely many \(n\); call it \(I_2\). Split \(I_2\) and repeat. This gives nested closed intervals \(I_1 \supseteq I_2 \supseteq \dots\) with \(I_k\) of length \(\frac{2M}{2^{k-1}}\), each containing infinitely many terms. By the nested interval property there is a point \(x\) in all of them. Now choose \(n_1\) with \(a_{n_1} \in I_1\), then \(n_2 > n_1\) with \(a_{n_2} \in I_2\) (possible because \(I_2\) holds infinitely many terms), and so on. Since both \(a_{n_k}\) and \(x\) lie in \(I_k\), \(|a_{n_k} - x| \le \frac{2M}{2^{k-1}} \to 0\). \(\blacksquare\)

The theorem does not say which subsequence converges or what its limit is, and a bounded sequence can have many subsequential limits. The sequence \(\sin n\) is bounded, and in fact every number in \([-1, 1]\) is the limit of some subsequence, because the integers modulo \(2\pi\) are dense in \([0, 2\pi]\). The boundedness hypothesis cannot be dropped: \(a_n = n\) has no convergent subsequence.

def monotone_subsequence(a):
    """Follow the peak proof on a finite list: return indices of a monotone subsequence."""
    n = len(a)
    peaks = [m for m in range(n) if all(a[m] >= a[j] for j in range(m + 1, n))]
    if len(peaks) >= 5:                      # many peaks: they decrease
        return "decreasing", peaks
    idx = [0]                                # few peaks: climb greedily
    while True:
        later = [j for j in range(idx[-1] + 1, n) if a[j] > a[idx[-1]]]
        if not later:
            return "increasing", idx
        idx.append(later[0])

import math
a = [math.sin(k) + 0.5 * (-1) ** k / (k + 1) for k in range(1, 61)]
kind, idx = monotone_subsequence(a)
print(kind, "subsequence of length", len(idx))
print("first terms:", [round(a[i], 3) for i in idx[:8]])
ok = all(a[idx[i]] <= a[idx[i + 1]] for i in range(len(idx) - 1)) if kind == "increasing" \
     else all(a[idx[i]] >= a[idx[i + 1]] for i in range(len(idx) - 1))
print("monotone:", ok)

decreasing subsequence of length 6
first terms: [1.076, 1.045, 1.024, 1.001, 0.628, -0.297]
monotone: True

Limit superior and limit inferior

For a bounded sequence, the set of subsequential limits has a largest and a smallest element. They have a direct description. Let \(s_n = \sup \{a_k : k \ge n\}\), the supremum of the tail from \(n\) on. As \(n\) increases the tail shrinks, so \((s_n)\) is decreasing, and it is bounded below. By the monotone convergence theorem it converges. Its limit is the limit superior,

\[\limsup_{n \to \infty} a_n = \lim_{n \to \infty} \sup_{k \ge n} a_k,\]

and similarly \(\liminf a_n = \lim_{n} \inf_{k \ge n} a_k\). For \((-1)^n\), every tail has supremum 1 and infimum \(-1\), so \(\limsup = 1\) and \(\liminf = -1\). One can show that a bounded sequence converges if and only if \(\limsup a_n = \liminf a_n\), and then both equal the limit. These quantities appear in the root test in lesson 6 and are developed further in MATH-341.

Comparing two descriptions of e

In calculus \(e\) is also given by the series \(\sum_{k=0}^{\infty} \frac{1}{k!}\). We can prove the two descriptions agree. Let \(t_n = \sum_{k=0}^{n} \frac{1}{k!}\). This sequence is increasing and bounded by 3, so it converges to some \(t\). The binomial expansion in the example showed \(e_n \le t_n\), so \(e \le t\) by the order limit theorem.

For the reverse inequality fix \(m\) and take \(n > m\). Keeping only the first \(m + 1\) terms of the binomial expansion of \(e_n\), all of which are positive,

\[e_n \ge \sum_{k=0}^{m} \frac{1}{k!}\Big(1 - \frac{1}{n}\Big)\cdots\Big(1 - \frac{k-1}{n}\Big).\]

As \(n \to \infty\) with \(m\) fixed, this finite sum tends to \(t_m\) by the limit laws, so \(e \ge t_m\). Letting \(m \to \infty\) gives \(e \ge t\). Hence \(e = t\). The series converges far faster than the product: \(t_{10}\) is already within \(3 \times 10^{-8}\) of \(e\), while \(e_{1000}\) is still off by more than \(10^{-3}\).

Behind this argument is a pattern we will use again: to compare two limits, fix one index, let the other go to infinity, and then release the first. It is a simple instance of exchanging limits, an operation that is not always allowed and that MATH-341 studies carefully under the name of uniform convergence.

Monotone sequences in computation

Many numerical algorithms produce monotone sequences, and the monotone convergence theorem is what guarantees they work. Bisection produces an increasing sequence of lower bounds and a decreasing sequence of upper bounds. The Babylonian method for square roots produces a decreasing sequence after the first step. Iterative methods for solving equations of the form \(x = f(x)\) often produce monotone sequences when \(f\) is increasing: if \(x_1 \le x_2\) then \(x_2 = f(x_1) \le f(x_2) = x_3\), and by induction the whole sequence increases. Combined with a bound, this proves convergence before we know the answer, and the recursion then identifies it.

When a sequence is monotone and bounded, its terms also give rigorous error bounds. For the Babylonian sequence, \(\sqrt{2} \le a_n\) and \(\frac{2}{a_n} \le \sqrt{2}\), so \(\sqrt{2}\) is trapped in \([\frac{2}{a_n}, a_n]\) and the width of this interval is a certified error. Interval arithmetic, used in computer-assisted proofs, is built on exactly this kind of enclosure.

Bolzano–Weierstrass is an existence theorem: it guarantees a convergent subsequence without saying which one or what its limit is. For the sequence \(\sin n\), for instance, the theorem promises convergent subsequences, and in fact every number in \([-1, 1]\) is the limit of one, because the multiples of 1 are dense modulo \(2\pi\). Finding an explicit subsequence converging to a given value requires number theory, namely good rational approximations to \(\pi\). The theorem itself needs none of that, which is exactly its strength in the existence proofs of lessons 6, 8 and 9.