(last updated: 4:06:50 PM, October 08, 2020)
A subsequence is like taking a sequence and discarding terms. We can discard a finite number of terms or even an infinite number of terms. We have already seen some simple subsequences: \(\{a_{n+1}\}_{n\in\mathbb N}\) is a subsequence of \(\{a_{n}\}_{n\in\mathbb N}\) since it is just discarding the first term.
Definition 2.6.1 (modified slightly) The sequence \(\{b_n\}_{n\in\mathbb N}\) is a subsequence of \(a_n\), if and only if there exists a strictly increasing function \(f:\mathbb N\rightarrow\mathbb N\) such that \(b_n=a_{f(n)}\) for all \(n\in\mathbb N\).
Note that \(b_1=a_{f(1)}, b_2=a_{f(2)},\ldots\) and that \(f(1)<f(2)<f(3)<\cdots\) is just a strictly increasing sequence of natural numbers.
We can even do things like discard all the even terms: \(\{a_{2n}\}_{n\in\mathbb N}\) is a subsequence of \(\{a_{n}\}_{n\in\mathbb N}\).
\[ \begin{aligned} &a_n: {\Huge\color{red}{_\times}}\!\!\!\!\!\!\!a_1,a_2, {\Huge\color{red}{_\times}}\!\!\!\!\!\!\!a_3,a_4, {\Huge\color{red}{_\times}}\!\!\!\!\!\!\!a_5,\ldots \\ &\qquad\qquad\text{ gives } \\ &a_{2n}: \quad a_2,a_4,a_6,a_8,\ldots \end{aligned} \]
We could even remove only terms whose indexes are prime \(\{a_n\}_{n\text{ is prime}}\) or a perfect square \(\{a_{n^2}\}_{n\in\mathbb N}\) or a power of two \(\{a_{2^n}\}_{n\in\mathbb N}\). There are limitless possibilities!
Sometimes taking a subsequence will make a calculation easier. We’ll see that subsequences can have nicer properties than their parent sequence but can still tell us something about the parent sometimes.
Sometimes we will have a sequence that may or may not converge, but we can stilll take a sort of upper extremal limit and a lower extremal limit. Consider \(a_n=(-1)^n\). This sequence doesn’t converge, but in some sense \(1\) is its long run upper bound and \(-1\) is its long run lower bound.
Also consider \(a_n=1+\frac1n\). It is bounded from above by 2 and from below by 1, but if we start chopping off finitely many terms, the remaining part of the sequence will still be bounded form below by 1 and we cannot refine that at all as arbitrarily large values of \(n\) get the sequence very close to 1. However we can refine our upper bound to less than 2 for the “tail” of the sequence. In fact, if we chop off enough terms, we can get our upper bound as close to 1 as we like. The “limiting upper bound” is in fact \(1\). Given any \(n^*\in\mathbb N\), the upper bound on \(\{a_n\}_{n\geq n^*}\) is exactly \(1+\frac1{n^*}\) and we can choose \(n^*\) as large as we wish to get this upper bound as close to 1 as we like.
The “limiting upper bound on the tail” is called the limit superior (and is denoted \(\limsup\)), and the “limiting lower bound on the tail” is called the limit inferior (and is denoted \(\liminf\)). Sometimes they go by other names such as upper limit and lower limit or limit supremum and limit infimum.
Definition 2.6.3 (modified) Let \(a_n\) be a sequence. Then we define \[\limsup_{n\rightarrow\infty} a_n=\lim_{n\rightarrow\infty}\left( \sup \{a_k \mid k\geq n\}\right)\] \[\liminf_{n\rightarrow\infty} a_n=\lim_{n\rightarrow\infty}\left( \inf \{a_k \mid k\geq n\}\right)\]
Sometimes you will see notation \(\overline{\lim}_{n\rightarrow\infty}\) for \(\limsup\) and \(\underline{\lim}_{n\rightarrow\infty}\) for \(\liminf\).
Often I just write \(\limsup a_n\) in place of \(\limsup_{n\rightarrow\infty} a_n\), and it should be understood that \(n\rightarrow\infty\) unless explicitly stated otherwise.
Example: Find the limit supremum and infimum of \(a_n=4+(-1)^n+\frac1n\).
\(\limsup_{n\rightarrow\infty} a_n=\lim_{n\rightarrow\infty}\left( \sup \{a_k \mid k\geq n\}\right)\)
Let \(S_n=\{a_k \mid k\geq n\}\). For example \[S_{10}=\{5+\frac1{10},3+\frac1{11},5+\frac1{12},\ldots,5+\frac1{2k},3+\frac1{2k+1},\ldots\}\] and \[S_{21}=\{3+\frac1{21},5+\frac1{22},3+\frac1{23},\ldots,3+\frac1{2k-1},5+\frac1{2k},\ldots\}\] Notice that as \(n\) gets large, the minimum of \(S_n\) will be close to \(3\) and its maximum will be close to \(5\). This gives you the intuition that \(\liminf a_n=3\) and \(\limsup a_n=5\).
Let \(n\) be a fixed natural number and consider the set \(S_n=\{4+(-1)^k+\frac1k \mid k\geq n\}\). Every number in this set is less than \(4+1+\frac1n =5+\frac1n\) because there will always be even numbers above any \(n\). In fact if \(n\) is even, then for \(k=n\) we have \(a_k=5+\frac1n\) is exactly the maximum of this set,a dn if \(n\) is odd, then we have the maximum is \(k=n+1\) and \(a_k=5+\frac1{n+1}\). These are the only two options. So the supremum of \(\{4+(-1)^k+\frac1k \mid k\geq n\}\) will always be either \(5+\frac1{n}\) or \(5+\frac1{n+1}\). Either way the limit of these as \(n\rightarrow \infty\) is \(5\). Thus \(\limsup_{n\rightarrow\infty} a_n=5\).
Similarly the infimum of this set will always be 3, since we can always choose very large \(k\) values to make \(\frac1k\) arbitrarily near \(0\) and \((-1)^k=-1\).
Thus \(\limsup_{n\rightarrow\infty} (4+(-1)^n+\frac1n)=5\) and \(\liminf_{n\rightarrow\infty} (4+(-1)^n+\frac1n)=3\)
Example: Find the limit superior and limit inferior of \[a_n= \begin{cases} 1-\frac1n & n \text{ even }\\ (-2)^n+\frac1n & n \text{ odd } \end{cases} \]
Notice that we can always find large, odd \(n\) values to make \((-2)^n\) an extremely large negative value, thus \(\liminf a_n=-\infty\). However, there will always be arbitrarily large even \(n\) values that give us sequence terms very close to \(1\), so \(\limsup a_n=1\).
Remark. Consider \(a_n\) that converges to \(A\). Then \(\limsup a_n=\liminf a_n=A\).
Remark. Consider \(a_n\) that diverges to \(+\infty\). Then \(\limsup a_n=\liminf a_n=+\infty\).
Note. Supremum and infimum of emptyset: \(\sup \emptyset=-\infty\) and \(\inf \emptyset=+\infty\).
Theorem 2.6.4 (Bolzano-Weierstrass Theorem for Sequences) Any bounded sequence must have at least one convergent subsequence.
Proof. Consider the set \(S=\{a_n\mid n\in\mathbb N\}\). This set is bounded and either contains infinitely many points or finitely many.
If it contains finitely many, then there is a real number \(A\) such that \(a_n=A\) for infinitely many \(n\). Let \(m_1\) be some index where \(a_n\) hits \(A\), i.e. \(a_{m_1}=A\). We know infinitely many choices exist for \(m_1\). Define \(f(1)\) by \(f(1)=m_1\). Then let \(m_2>m_1\) be some future index where \(a_{m_2}=A\) again, and define \(f(2)=m_2\). We know that this will occur infinitely many times, so if we are at \(f(k)=m_k\), we can always choose a value for \(m_{k+1}=f(k+1)>f(k)=m_k\) such that \(a_{m_{k+1}}=A\). By induction \(a_{f(n)}\) exists for all \(n\in\mathbb N\) and by construction \(a_{f(n)}=A\) for all \(n\). Thus we have constructed a subsequence \(a_{f(n)}\) that converges to \(A\) (it is a constant sequence).
Here is a sketch of the proof for the case that \(S\) contains infinitely many points, then we know it has an accumulation point. Construct a subsequence of \(a_n\) by picking any index value for \(f(1)\). Then proceed as in the proof of Theorem 2.5.4 (Bolzano Weierstrass Theorem for sets) splitting the interval in two pieces and picking the next term of the subsequence form the new piece that still has infinitely many points left. In this way we will construct a subsequence \(a_{f(n)}\) that converges to an accumulation point. \(\blacksquare\)
Example: We can extract convergent subsequences from \(a_n=(-1)^n\). Consider \(a_{2n}=1\) and \(a_{2n-1}=-1\). Of course these are not the only convergent subsequences we can construct. Let \(f(n)\) be arbitrarily defined for \(n=1,2,3,\ldots, k\) given some finite \(k\in\mathbb N\). Then let \(f(n)\) be any sequence of even numbers above \(k\). Then \(a_{f(n)}=1\) eventually and thus converges to 1.
An unbounded or ocillatory sequence can also have convergent subsequences.
Example: \[a_n= \begin{cases} n & n \text{ even}\\ \frac1n & n \text{ odd} \end{cases} \]
Then \(a_{2n}\rightarrow+\infty\) and \(a_{2n-1}\rightarrow0\).
Example: Let \(q_n\) be a sequence of all rational numbers. Recall that the rational numbers are countable and so can be listed out: \(q_1,q_2,\ldots\). Then for any real number \(x\in\mathbb R\), there is a subsequence \(q_{f(n)}\) that converges to \(x\). This is really mind blowing actually. Recall that \(\mathbb Q\) is dense in \(\mathbb R\) meaning that for any \(\epsilon>0\), and any \(n^*\) are infinitely many \(q_n\) with \(n\geq n^*\) that are within \(\epsilon\) of \(x\).
Theorem 2.6.5 A sequence converges to \(A\) if and only if each of its subsequences converges to \(A\).
See the textbook for proof.
Note that this must be true for ALL subsequences. We can test one or two subsecuences and show that they converge to the same limit and conclude that the sequence converges!
Counterexample: Consider
\[a_n= \begin{cases} (-1)^n & n \text{ a multiple of 5}\\ 1+\frac1n & n \text{ not a multiple of 5} \end{cases} \] We have that \(a_{f(n)}\rightarrow 1\) as long as \(f(n)\) is never a multiple of \(5\), but the sequence \(a_n\) does not converge. In particular the subsequence \(a_{5n}=(-1)^{5n}\) does not converge.
\[ \diamond \S \diamond \]