Subsequences and convergence

If \(a_n\) is a sequence of real numbers, and \(n_k\) is a sequence of natural numbers that is increasing (that is, :math:`n_{k+1} > n_k), then we can define a sequence \(a_{n_k}\). This is called a subsequence of \(a_n\).

Subsequences interact with convergence in a few interesting ways. First, if \(a_n\) converges to \(a\), then every subsequence does as well.

To prove this, we will first show a useful lemma: if \(n_k\) is an increasing sequence of natural numbers, than \(n_k \geq k\). We show this by induction: \(n_0\) is a natural number, so by definition, \(n_0 \geq 0\). Assume \(n_k \geq k\), then \(n_{k+1} > n_k \geq k\). Since \(n_{k+1} > k\), then \(n_{k+1} \geq k+1\).

Now, let \(\epsilon > 0\). Since \(a_n\) converges to \(a\), there is an \(N\) such that \(n > N\) implies \(|a_n - a| < \epsilon\). Now, if \(k > N\), then \(n_k > N\), so \(|a_{n_k} - a| < \epsilon\). Since this is true for every \(\epsilon\), we have proved the subsequence converges.

Since \(a_n\) is a subsequence of itself (via :math`n_k = k`), if every subsequence converges to \(a\), than so does \(a_n\). Note that if \(a_n\) converges to \(a\), then so does every subsequence as shown above, and therefore, so does every subsubsequence. In fact, a weaker result is true: if every subsequence has a subsubsequence that converges to \(a\), than so does \(a_n\).

In order to prove this, we need to master a technique that is mechanical yet subtle: reversing complicated statements. We need to specify what it means for a sequence to not converge to \(a\). If \(a_n\) does not converge to \(a\), then there exists an \(\epsilon > 0\) such that for every \(N\) there is an \(n>N\) such that \(|a_n - a| \geq \epsilon\).

The easiest way to approach the theorem is to prove the logical converse: if \(a_n\) does not converge to \(a\), then there is a subsequence with no subsubsequence that converges to \(a\).

Let \(a_n\) be a sequence, and let us assume \(a_n\) does not converge to \(a\). Let \(N = 0\). Then we can find, as above, :math`n_0`, so that \(|a_{n_0} - a| \geq \epsilon\). Now we define a subsequence recursively: let \(N=n_k\), find \(n_{k+1} > N\) such that \(|a_{n_{k+1}} - a| \geq \epsilon\). Note that since every element of this subsequence is \(\epsilon\)-away from \(a\), than no subsubsequence can converge to \(a\).

We note that here we did not take advantage of the properties of real numbers, and indeed, the above results are true for rational numbers as well. The following result is not (and, indeed, it is possible to show that it is unique to the real numbers).

Let \(a_n\) be a bounded sequence, -M<a_n<M for every :math:` n`. Then it has a converging subsequence. Since this result is so important, both for understanding real numbers and, practically, to prove results about real numbers, there will be too proofs given.

We define two sequences, \(c_k\) increasing and \(d_k\) decreasing, by induction, with the property that there is an infinite number of \(a_n\) such that :math:` c_kleq a_nleq d_k` for every :math:` k`. We set :math:` c_0=-M,d_0=M`. Since all \(a_n\) satisfy that, an infinite number of them do. Assume we have \(c_k<d_k\). Set \(m=(c_k+d_k)/2\). Assume a finite number of :math:` a_n` have :math:` c_nleq a_nleq m`[1] and a finite nmber of :math:` a_n` have :math:` mleq a_nleq d_n`[2]. However every :math:` a_n` is either :math:` leq m` or :math:` geq m`, so only a finite number of :math:` a_n` have \(c_k\leq a_n\leq d_k\). This contradicts the inductive assumption, so one of [1] or [2] is infinite. If [1] is infinite, set :math:` c_{k+1}=c_k,d_{k+1}=m` otherwise :math:` c_{k+1}=m,d_{k+1}=d_k`. We see that \(d_k-c_k=1/2^k\) and so converges to \(0\).

We apply Cantor’s lemma, and get \(c_k\) and \(d_k\) converge to \(a\). Set \(n_0 = 0\). Then \(c_0 = -M < a_{n_0} < M = d_0\). Recursively, find \(n_{k+1} > n_k\) such that \(c_{k+1} \leq a_{n_{k+1}} \leq d_{k+1}\). One such must exist, because there are infinite members of \(a_n\) between \(c_{k+1}\) and \(d_{k+1}\), but only a finite number \(\leq n_k\).

By the Sandwich theorem, we have :math:` a_{n_k}` converging to :math:` a`.

Here is another proof for this: let \(a_n\) be any sequence. We define a subsequence by induction: let \(n_0\) be such that a_{n_0} is less than any element in the sequence. Let \(n_{k+1}\) be such that it is :math:` >n_k` and the smallest element that is :math:` geq` than a_{n_k}. If this construction succeeds, we have an increasing subsequence. This construction might fail: at any stage, the “smallest” element might not exist. However, if the smallest element does not exist, we define a new subsequence, \(m_k\). Without loss of generality, we assume that the smallest element does not exist in the first stage: therefore, for every \(n\), \(a_n\) is not the smallest element. We take \(m_0\) to be \(0\). If we have \(m_k\), we notice there must be an infinite number of \(m\), \(a_m < a_{m_k}\).

This means for every sequence, we can either construct an increasing subsequence or a decreasing subsequence. Since bounded increasing or decreasing sequences, we constructed a converging subsequence.