2.8 Subsequences and the Bolzano–Weierstrass theorem

Even though the sequence $((-1)^{n})_{n\in\mathbb{N}}$ does not converge, we observed that it does have convergent subsequences, such as the subsequence $(1)_{k\in\mathbb{N}}$ consisting of all even terms. The following theorem is a vast generalisation of this observation.

Theorem 2.74 (Bolzano–Weierstrass).

Every bounded sequence of real numbers has a convergent subsequence.

This is a powerful result, because it allows us to deduce the existence of convergent subsequences without having to explicitly find them. For instance, since $-1\leq\sin n\leq 1$ for all $n\in\mathbb{N}$ , the sequence $(\sin n)_{n\in\mathbb{N}}$ is bounded. We can therefore deduce from the Bolzano–Weierstass theorem that $(\sin n)_{n\in\mathbb{N}}$ has a convergent subsequence. Finding an explicit convergent subsequence is not so easy, however!

Exercise 2.75.

Show that the condition that the sequence is bounded is necessary to guarantee the conclusion of Theorem 2.74. More precisely, find an example of an unbounded sequence $(a_{n})_{n\in\mathbb{N}}$ which has no convergent subsequence.

Here we give a proof which is a nice application of the monotone convergence theorem. We shall need the following preliminary lemma.

Lemma 2.76.

Every sequence has a monotone subsequence.

We postpone the proof of Lemma 2.76 and first show how it can be used to prove Theorem 2.74.

Proof (of Theorem 2.74).

Let $(a_{n})_{n\in\mathbb{N}}$ be a bounded sequence, so that there exists some $M>0$ such that $|a_{n}|\leq M$ for all $n\in\mathbb{N}$ . By Lemma 2.76, there must exist a monotone subsequence $(a_{n_{k}})_{k\in\mathbb{N}}$ . Furthermore, $|a_{n_{k}}|\leq M$ for all $k\in\mathbb{N}$ , so that $(a_{n_{k}})_{k\in\mathbb{N}}$ is also bounded. Thus, by the monotone convergence theorem, the subsequence $(a_{n_{k}})_{k\in\mathbb{N}}$ converges, as required. ∎

We now turn to the details of Lemma 2.76. A useful thought experiment is to try to construct a sequence for which the lemma fails: that is, try to find a sequence which has no monotone subsequence. After some effort, you should become reasonably convinced that no such sequence can exist, but it is more challenging to turn this intuition into a formal proof.

Figure 2.9: A sequence

(a_{n})_{n\in\mathbb{N}}

with peaks at

n=4

5

14

18

. For instance,

14

is a peak since all subsequent terms

a_{n}

for

n>14

lie in the yellow region below the line

y=a_{14}

Proof (of Lemma 2.76).

We shall say $p\in\mathbb{N}$ is a peak if $a_{p}\geq a_{n}$ for all $n\in\mathbb{N}$ with $n\geq p$ ; we illustrate this concept in Figure 2.9. The proof splits into two cases, depending on the number of peaks.

Case 1: Suppose there exist infinitely many peaks. Then we can find an increasing sequence of natural numbers $n_{1}<n_{2}<n_{3}<\cdots$ such that $n_{k}$ is a peak for all $k\in\mathbb{N}$ . By definition of a peak, $a_{n_{1}}\geq a_{n_{2}}\geq a_{n_{3}}\geq\cdots$ and so the subsequence $(a_{n_{k}})_{k\in\mathbb{N}}$ is non-increasing and therefore monotonic.

Case 2: Suppose there exist finitely many peaks. Then we can find some $n_{1}\in\mathbb{N}$ such that $p<n_{1}$ for every peak $p\in\mathbb{N}$ . In particular, $n_{1}$ is not a peak and so there must exist some $n_{2}\in\mathbb{N}$ with $n_{2}>n_{1}$ such that $a_{n_{2}}>a_{n_{1}}$ . However, $n_{2}$ is also not a peak, so there must exist some $n_{3}\in\mathbb{N}$ with $n_{3}>n_{2}$ such that $a_{n_{3}}>a_{n_{2}}$ . Continuing in this way, we construct an increasing sequence of natural numbers $n_{1}<n_{2}<n_{3}<\cdots$ such that $a_{n_{1}}<a_{n_{2}}<a_{n_{3}}<\cdots$ . Thus, the subsequence $(a_{n_{k}})_{k\in\mathbb{N}}$ is increasing and therefore monotonic. ∎