4.4 Subsequences

Now we want to introduce the idea of a subsequence, which is a sequence contained within another sequence. We can do this by taking a regular old sequence of real numbers and ‘picking’ certain entries out that we want to be part of the new subsequence, for example: every 2nd entry, every 5th entry, every entry whose index is a power of 10. We can do this by defining a new sequence of natural numbers, and then using this sequence to index our original one as follows.

Definition 4.4.

Let $(x_{n})_{n}$ be a sequence of real numbers and $(m_{k})_{k}$ be a sequence of natural numbers which is strictly increasing $(m_{1}<m_{2}<m_{3}<\dots)$ . Then $(x_{m_{k}})_{k}$ is a subsequence of $(x_{n})_{n}$ .

So, for example, we could start with the sequence $(x_{n})_{n}=\left(\frac{1}{n^{2}}\right)_{n}$ and take $m_{k}=2k$ , then $x_{m_{k}}=x_{2k}=\frac{1}{(2k)^{2}}$ . One important thing to note from this definition is that we always have $m_{k}\geq k\ \forall k\in\mathbb{N}$ , this will be a useful fact going forward. Now, how can we know if a subsequence converges? We can use the methods we have discovered already, but also it turns out that if a sequence is convergent then any subsequence of it will also converge to the same limit.

Theorem 4.6

Let $(x_{n})_{n}$ be a convergent subsequence with $x_{n}\to x$ as $n\to\infty$ . Then any subsequence $(x_{m_{k}})_{k}$ also has $x_{m_{k}}\to x$ as $k\to\infty$ .

Proof.

Let $\varepsilon>0$ . Since $x_{n}\to x,\ \exists N\in\mathbb{N}$ such that $n\geq N\implies\lvert x_{n}-x\rvert<\varepsilon$ . Since $(x_{m_{k}})_{k}$ is a subsequence of $(x_{n})_{n}$ , we can let $K\in\mathbb{N}$ such that for $k\geq K$ we have $m_{k}\geq N$ (for example, choose $K=N$ since $m_{k}\geq k\geq N$ ). Then we have

\lvert x_{m_{k}}-x\rvert<\varepsilon\ \forall k\geq K,

(4.40)

which means that the subsequence converges to $x$ . ∎

4.4.1 Bolzano-Weierstrass Theorem

Theorem 4.7 (Monotone Subsequence Theorem)

Any sequence of real numbers has a monotone subsequence.

Proof.

Let $(x_{n})_{n}$ ba a sequence of real numbers. Before proving this theorem we make a quick definition. We say that a natural number $p$ is a peak if $x_{p}\geq x_{n}\ \forall n\geq p$ , i.e. it is the index of the greatest number in the sequence from that point onwards. Now, there are two cases for a general sequence: either it has infinitely many peaks, or it has finitely many.
Case 1: $(x_{n})_{n}$ has infinitely many peaks. List out the peaks in order of which they occur — $p_{1}<p_{2}<p_{3}\dots$ — and notice that by definition we have

x_{p_{1}}\geq x_{p_{2}}\geq x_{p_{3}}\geq\dots,

(4.41)

and thus $(x_{p_{k}})_{k}$ is a decreasing subsequence (which is monotone) as required.
Case 2: $(x_{n})_{n}$ has finitely many peaks. Again we can list them in order: $p_{1}<p_{2}<p_{3}<\dots<p_{N}$ . Now let $t_{1}>p_{N}$ be a natural number. Since $t_{1}$ is not a peak by definition, there exists $t_{2}>t_{1}$ such that $x_{t_{2}}>x_{t_{1}}$ . Since $t_{2}$ is also not a peak, there exists $t_{3}>t_{2}$ such that $x_{t_{3}}>x_{t_{2}}$ . Continuing in this way we generate a sequence $t_{1}<t_{2}<t_{3}<\dots$ with $x_{t_{1}}<x_{t_{2}}<x_{t_{3}}<\dots$ , hence $(x_{t_{k}})_{k}$ is an increasing subsequence (which is monotone) as required. ∎

Notice that if we wanted to create an increasing subsequence from a sequence with infinitely many peaks, or a decreasing subsequence from one with finitely many, we need only switch round the definition of a peak to that of a ‘trough’ by flipping the order relation and also flipping all the order relations in the body of the proof. Thus no generality is lost. We will now prove one of the major results of real analysis using all of the tools we have gathered so far.

Theorem 4.8 (Bolzano-Weierstrass Theorem)

Any bounded sequence of real numbers has a convergent subsequence.

Proof.

Let $(x_{n})_{n}$ be any bounded sequence of real numbers. Then by the Monotone Subsequence Theorem (4.7), $(x_{n})_{n}$ has a monotone subsequence $(x_{m_{k}})_{k}$ . But now this subsequence is both monotone and bounded, so by the Monotone Convergence Theorem (4.5), this subsequence is convergent. ∎

A simple example of this theorem in action would be the sequence $((-1)^{n})_{n}$ , which is bounded but does not converge, however the subsequence $((-1)^{2k})_{k}=(1)_{k}$ does converge.