1. Subsequences
Given a sequence \(\{a_n\}_{n=1}^\infty\), a subsequence is any other infinite sequence which runs through any subcollection of terms of the original sequence in order. This is most easily indicated by letting \(\{n_i\}_{i=1}^\infty\) be a strictly increasing sequence of positive integers and then considering the new sequence \(\{a_{n_i}\}_{i=1}^\infty\). If the \(n_i\) are not strictly increasing, then \(\{a_{n_i}\}_{i=1}^\infty\) is not considered a subsequence of \(\{a_n\}_{n=1}^\infty\).
Example
Consider the sequences below.
\[{} 1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \ldots{}\]
\[{}\frac{1}{2}, \frac{1}{8}, \frac{1}{32}, \frac{1}{128},\ldots{}\]
The lower sequence is a subsequence of the upper one. If \(\{a_n\}_{n=1}^\infty\) denotes the upper sequence, then the lower sequence can be written as \(\{a_{n_i}\}_{i=1}^\infty\) where \(n_i := 2i - 1\) for each \(i\).
The act of taking subsequences is often a useful way to produce a new sequence with nicer properties than the original. The most important theorem demonstrating this idea is the Bolzano-Weierstrass Theorem (below). Subsequences often automatically inherit properties from the original sequence as well. For example:
Theorem
Every subsequence of a monotone sequence is itself monotone.
Theorem
Every subsequence of a convergent sequence is itself convergent and has the same limit as the original.
Proof
Let \(\{a_n\}_{n=1}^\infty\) be a convergent sequence with limit \(L\) and let \(\{a_{n_i}\}_{i=1}^\infty\) be a subsequence. For any \(\epsilon > 0\), there must be some \(N\) such that \(|a_n - L| < \epsilon\) for all \(n > N\). We claim that there must also be some \(I\) such that \(|a_{n_i} - L| < \epsilon\) for all \(i > I\). To see why, first note that the map \(i \mapsto n_i\) is injective because it is strictly increasing. This means that its image must be countably infinite. In particular, its image cannot be contained in \(\{1,\ldots,N\}\) because this is a finite set. So there must be some \(I\) such that \(n_{I} > N\). Now because \(n_i\) is monotone, when \(i > I\), \(n_i > n_{I} > N\). Thus, for every \(i > I\), \(n_i > N\) and consequently \(|a_{n_i} - L| < \epsilon\) as desired.
1.1. A Side Note on Inductive Definitions
It often happens that subsequences are defined inductively, meaning that there is some property that the \(i\)-th term of the subsequence is chosen to possess assuming that all the preceding terms have already been chosen. Assuming some basic compatibility rules of the underlying properties, this is a perfectly acceptable way to construct subsequences.
Theorem (Inductive Definitions)
Suppose \(E\) is some countable set and that for each \(N \in {\mathbb N}\), \(P_N\) is some nonempty collection of functions \(f \ : \ \{1,\ldots,N\} \rightarrow E\) such that the collection of functions obtained by restricting those \(f \in P_{N+1}\) to \(\{1,\ldots,N\}\) is exactly \(P_N\) (so in other words, the restriction of every \(f \in P_{N+1}\) to \(\{1,\ldots,N\}\) belongs to \(P_N\) and every \(f' \in P_N\) is the restriction of some \(f \in P_{N+1}\)). Then there is some function \(f \ : \ {\mathbb N} \rightarrow E\) such that \(f\) restricted to \(\{1,\ldots,N\}\) belongs to \(P_N\) for each \(N \in {\mathbb N}\).
Proof
Without loss of generality, assume that \(E = {\mathbb N}\). For each \(N\), let \(Q_N \subset P_N\) consist of those functions \(f \in P_N\) such that \(g(i) \leq f(i)\) for each \(i \in \{1,\ldots,N\}\) and \(g \in P_N\) implies \(g = f\). In other words, \(Q_N\) contains those \(f \in P_N\) for which reducing any of the values of \(f\) produces a function no longer in \(P_N\).
We will show that \(Q_N\) contains exactly one element for each \(N\) and the element \(f \in Q_N\) agrees with the corresponding element \(f' \in Q_{N-1}\) when restricted to \(\{1,\ldots,N-1\}\). The proof is by induction. If \(N=1\), \(P_1\) is simply some nonempty subset of functions \(f \ : \ \{1\} \rightarrow {\mathbb N}\). Of all the values attained by such functions in \(P_1\), there must be a smallest value \(n_0\) because the natural numbers are well-ordered. Consequently the function \(f\) with \(f(1) = n_0\) must belong to \(Q_1\) since \(g \in P_1\) and \(g(1) \leq f(1)\) implies \(g(1) \leq n_0\), making \(g(1) = n_0 = f(1)\). Moreover, \(Q_1\) contains exactly one element.
By induction, suppose that \(Q_N\) contains exactly one element and restricts to the unique element of \(\{1,\ldots,N-1\}\) in \(Q_{N-1}\). Let \(P_{N+1}'\) be the subset of those functions in \(P_{N+1}\) which belong to \(Q_N\) when restricted to the domain \(\{1,\ldots,N\}\). Because \(Q_N\) is known to be nonempty, \(P_{N+1}'\) is also guaranteed to be nonempty. Because \(Q_N\) has exactly one element, all functions in \(P_{N+1}'\) agree on \(\{1,\ldots,N\}\). Once again, let \(n_0\) be the smallest value \(f'(N+1)\) attained by some \(f' \in P_{N+1}'\). There is a unique function \(f' \in P_{N+1}'\) with \(f'(N+1) = n_0\). Now suppose \(g'(i) \leq f'(i)\) for each \(i \in \{1,\ldots,N+1\}\) and that \(g' \in P_{N+1}\). If one can show that any such \(g'\) must equal \(f'\), then \(f' \in Q_{N+1}\) and the induction proof that \(Q_N\) always contains one element is finished. So suppose there is some \(i_0 \in \{1,\ldots,N+1\}\) for which \(g'(i_0) < f'(i_0)\). If \(i_0 < N+1\), then the restrictions of \(g'\) and \(f'\) to \(\{1,\ldots,i_0\}\) both both belong to \(P_{i_0}\) and \(f'\) restricts to the unique element in \(Q_{i_0}\), so there is a contradiction of the inequality \(g'(i_0) < f'(i_0)\). Thus \(i_0 = N+1\). But now \(g'(i_0) < n_0\) is impossible because \(g'\) agrees with \(f'\) on \(\{1,\ldots,N\}\) and \(n_0\) is the smallest possible value that any such function can take at \(i = N+1\) when extended in such a way as to belong to \(P_{N+1}\).
Now let \(f : {\mathbb N} \rightarrow {\mathbb N}\) be given by \(f(N) = f_N(N)\), where \(f_N\) is the unique element of \(Q_N\). Because \(f_n\) restricts to \(f_{N'}\) on \(\{1,\ldots,N'\}\) when \(N' < N\), it follows that \(f_{N'}(N') = f_N(N')\) when \(N' \leq N\). As a consequence, \(f\) restricts on \(\{1,\ldots,N\}\) to equal exactly \(f_N \in Q_N \subset P_N\).
As an example, we have the following corollary:
Corollary
Suppose that \(I_1,I_2,I_3,\ldots\) are subsets of the real numbers and that \(\{a_n\}_{n=1}^\infty\) is a sequence of real numbers such that for each \(j\), \(a_n \in I_j\) for infinitely many values of \(n\). Then there exists a subsequence \(\{a_{n_j}\}_{j=1}^\infty\) such that \(a_{n_j} \in I_j\) for each \(j\).
Proof
Let \(P_N\) be the collection of strictly increasing sequences \((n_1,\ldots,n_N)\) such that \(a_{n_j} \in I_{j}\) for each \(j\). Restricting a sequence in \(P_N\) by dropping the last term clearly produces a sequence in \(P_{N-1}\). Likewise \(P_1\) is nonempty because there are infinitely many values of \(n\) with \(a_n \in I_1\). Similarly, if \((n_1,\ldots,n_N) \in P_N\), there are infinitely many values of \(n\) such that \(a_n \in I_{N+1}\), and so in particular there must be values of \(n\) with \(n > n_{N}\) and \(a_n \in I_{N+1}\). Letting \(n_{N+1}\) be any such value of \(n\) gives a new sequence \((n_1,\ldots,n_{N+1}) \in P_{N+1}\). So in particular, none of the sets \(P_N\) are empty and they have the desired relationships with respect to restriction. Thus by the theorem, there exists a sequence \(\{n_j\}_{j=1}^\infty\) such that \((n_1,\ldots,n_N)\) belongs to \(P_N\) for each \(N\). This forces \(\{n_j\}_{j=1}^\infty\) to be strictly increasing and to have \(a_{n_j} \in I_j\) for each \(j\) as desired.
2. Bolzano-Weierstrass
Proof Step 1: Nested Intervals Suppose \(\{a_n\}_{n=1}^\infty\) is our bounded sequence. For convenience, assume that \(M\) is the real number such that \(|a_n| \leq M\) for all \(n\). In other words, \(a_n \in [-M,M]\) for all \(n \in {\mathbb N}\).
- Let \(I_0 := [-M,M]\) (i.e., we're just giving this interval a name). We know that \(a_n \in I_0\) for all \(n\), so in particular \(a_n \in I_0\) for infinitely many distinct values of \(n\).
- Subdivide \(I_0\) into left and right halves: \(L := [-M,0]\) and \(R := [0,M]\). At least one of \(L\) and \(R\) must also have the property that it contains \(a_n\) for infinitely many values of \(n\). (If not, there would be only finitely many \(n\) such that \(a_n \in L \cup R\), but \(L \cup R = I_0\).) We'll define a new interval \(I_1\) as follows: if \(L\) contains \(a_n\) for infinitely many values of \(n\), then take \(I_1 := L\). Otherwise take \(I_1 := R\).
- We can easily see that \(I_1 \subset I_0\), the length of \(I_1\) is half the length of \(I_0\), and \(a_n\) belongs to \(I_1\) for infinitely many values of \(n\).
We may now inductively define a sequence of intervals \(I_0 \supset I_1 \supset I_2 \supset \cdots\) with the property that the length of \(I_j\) is \(2^{-j}\) times the length of \(I_0\) and \(a_n\) belongs to \(I_j\) for infinitely many values of \(n\). Assuming that \(I_0,\ldots,I_{j-1}\) have already been defined,
- Subdivide \(I_{j-1}\) into left and right halves \(L\) and \(R\). At least one of \(L\) and \(R\) must also have the property that it contains \(a_n\) for infinitely many values of \(n\). (If not, there would be only finitely many \(n\) such that \(a_n \in L \cup R\), but \(L \cup R = I_{j-1}\).) We'll define a new interval \(I_j\) as follows: if \(L\) contains \(a_n\) for infinitely many values of \(n\), then take \(I_j := L\). Otherwise take \(I_j := R\).
To be extremely pedantic, we would need to use the theorem on inductive definitions above (or something like it) to verify that this process of constructing intervals \(I_0 \supset I_1 \supset I_2 \supset I_3 \supset \cdots\) produces an actual infinite sequence of intervals rather than just some family of finite sequences of unbounded length (i.e., each sequence finite but no limit on how long the finite sequence can be). In this case, we can apply the theorem by thinking of each interval \(I_j\) as being produced by some finite list of choices of left versus right (with the number of choices being equal to \(j\)). The theorem then guarantees that there is some never-ending sequence of choices which at each stage yields a valid \(I_j\).
Proof Step 2: Identifying a Candidate for the Limit We need to find not only a convergent subsequence, but also the value of its limit. The idea is roughly to take a subsequence of terms belonging to \(I_1, I_2, I_3,\ldots\), but even assuming the technical issues there are resolved, what is the limit? We can use the intervals themselves to identify the limit point.
For each \(j\), let \(x_j\) and \(y_j\) denote the endpoints of \(I_j\), i.e., \(I_j = [x_j,y_j]\). Because the intervals are nested, if \(j \leq j'\) then \([x_j,y_j] \subset [x_{j'},y_{j'}]\), which means that \(x_{j'} \leq x_j < y_j \leq y_{j'}\). Just by taking \(j' := 1\), this implies that the sequence \(\{x_{j}\}_{j=1}^\infty\) is nondecreasing and bounded above. Likewise \(\{y_j\}_{j=1}^\infty\) is nonincreasing and bounded below. Both sequences must therefore be convergent. Moreover, \(y_j - x_j = 2^{1-j} M\) which converges to zero as \(j \rightarrow \infty\). Thus \(\lim_{j \rightarrow \infty} (x_j - y_j) = 0\) and consequently \(\lim_{j \rightarrow \infty} x_j = \lim_{j \rightarrow \infty} y_j\). Let \(L\) denote this limit, i.e.,
\[ L := \lim_{j \rightarrow \infty} x_j = \lim_{j \rightarrow \infty} y_j.\]
Proof Step 3: Picking a Subsequence The subsequence we will take will be one with the property that \(a_{n_j} \in I_j\) for each \(j\). Formally, its existence is guaranteed by the corollary above. Somewhat less formally, the process by which it is constructed is to take \(n_1\) so that \(a_{n_1} \in I_1\) (which is possible because \(a_n \in I_1\) for infinitely many \(n\)), then inductively taking \(n_j > n_{j-1}\) such that \(a_{n_j} \in I_j\) (which is possible because \(a_n \in I_j\) for infinitely many \(j\), so throwing out those \(n \leq n_{j-1}\) does not exclude all possible options).
Proof Step 4: Showing the Subsequence Converges to the Limit Now because \(a_{n_j} \in I_j\) for each \(j\), \(x_j \leq a_{n_j} \leq y_j\) for each \(j\). In particular, \(x_j - L \leq a_{n_j} - L \leq y_j - L\) for each \(j\). Now for any \(\epsilon > 0\), there exist \(N_1\) and \(N_2\), respectively, such that \(j > N_1\) gives \(|x_j - L| < \epsilon\) and \(j > N_2\) gives \(|y_j - L| < \epsilon\). If \(j > \max\{N_1,{\mathbb N}_2\}\), then, one has that
\[ - \epsilon < x_j - L \leq a_{n_j} - L \leq y_j - L < \epsilon, \]
meaning \(|a_{n_j} - L| < \epsilon\). Thus \(a_{n_j} \rightarrow L\) as \(j \rightarrow \infty\).
Exercises
- If \(\{a_n\}_{n=1}^\infty\) is a bounded sequence, must every subsequence be convergent? Prove or give a counterexample.
- Give an example of a bounded sequence \(\{a_n\}_{n=1}^\infty\) for which there are at least three convergent subsequences, each with a different limit than the other two.