Most of what follows is taken from Rudin's book Principles of Mathematical Analysis.
The concept of upper and lower limits (commonly denoted by \(\limsup\) and \(\liminf\) respectively) shows up routinely when discussing the limiting behaviour of a sequence. For example, consider the Big O notation, \(\mathcal{O}\), defined as \(f(n) = \mathcal{O}(g(n))\) iff there exists a positive real number \(c\) and an integer \(N\) such that for every \(n \in \Z\), \(n > N\), we have \(|f(n)| \leq c g(n)\). This can be succinctly written as
In this post, I aim to expound on the concept of upper and lower limits so that the second formulation of Big O notation above becomes just as natural as the first one.
I start with some definitions.
Note: The symbol \(\to\) is now used for certain type of divergent sequences as well.
It immediately follows that \(s_* \leq s^*\).
The fact that \(E\) is non-empty (and thus taking \(\sup\) or \(\inf\) makes sense) follows from the observation that either \(\{s_n\}\) is bounded or unbounded. If it is bounded then it must contain a convergent subsequence (by the Bolzano–Weierstrass theorem) and thus at least one element, or if it is unbounded then it must contain either \(+\infty\) or \(-\infty\).
Now let us prove some lemmas that will be useful later.
As before, let \(E\) be the set of all subsequential limits of \(\{p_n\}\) and let \(q\) be a limit point of \(E\). We have to show that \(q \in E\). To show this we will construct a subsequence of \(\{p_n\}\) which converges to \(q.\)
Choose \(n_1\) so that \(p_{n_1} \neq q\). If no such \(n_1\) exists, then \(E\) has only one element, namely \(q = p_1 = p_2 = \cdots\), and there is nothing to prove. Define \(\delta = d(q, p_{n_1})\). Suppose \(n_1, \ldots, n_{i-1}\) for some fixed \(i \ge 2\) are chosen. Since \(q\) is a limit point of \(E\), there is a point \(x \in E\) with \(d(q, x) < \delta /2^i\). Since \(x \in E\), there is an \(n_i > n_{i-1}\) such that \(d(x, p_{n_i}) < \delta/2^i\). Thus
We now have all the tools to prove the highlight of this blog post, a very useful characterization of upper and lower limits.
Theorem 1: Let \(\{s_n\}\) be a sequence of real numbers. Let \(E\) and \(s^*\) have the same meaning as previously. Then \(s^*\) has the following two properties:
\(s^* \in E\), and
if \(x > s^*\), then there exists an integer \(N\) such that \(n \geq N\) implies \(s_n < x.\)
Moreover, \(s^*\) is the only number with these two properties.
Of course, an analogous result is true for \(s_*\).
We start by showing the two properties.
We divide it into three cases depending on what value \(s^*\) takes:
If \(s^* = +\infty\), then \(E\) is not bounded above, hence \(\{s_n\}\) is not bounded above, and thus there is a subsequence \(\{s_{n_k}\}\) such that \(s_{n_k} \to +\infty.\) Therefore, \(+\infty \in E\), or in other words \(s^* \in E\).
If \(s^*\) is real, then \(E\) is bounded above, and at least one subsequential limit exists by the definition of \(\sup\). **Therefore, \(s^* \in E\) follows from the Lemmas 1 and 2, and the fact that \(s^* = \sup E.\)
Lastly, if \(s^* = -\infty\), then \(E\) contains only one element, namely \(-\infty\), and there is no subsequential limit. Thus, \(s^* \in E\).
Suppose for the sake of contradiction that there is a number \(x > s^*\) such that \(s_n \geq x\) for infinitely many values of \(n\). Let's denote this set of \(n\)'s with \(\mathcal{K}\) and let \(\{s_k\}_{k \in \mathcal{K}}\) be this subsequence. If \(\{s_k\}_{k \in \mathcal{K}}\) is unbounded then \(s^* = +\infty\) contradicting the fact that there exists an \(x > s^*.\) And if \(\{s_k\}_{k \in \mathcal{K}}\) is bounded that it contains a convergent subsequence (by the Bolzano–Weierstrass theorem). Suppose this convergent subsequence converges to \(y\). Then \(y \geq x > s^*\). This contradicts the definition of \(s^*.\)
To show the uniqueness, suppose there are two distinct numbers, \(p\) and \(q\), which satisfy the two properties, and suppose \(p < q\). Choose \(x\) such that \(p < x < q\). Since \(p\) satisfies the second property, there exists an integer \(N\) such that \(s_n < x\) for \(n \geq N\). But then \(q\) cannot satisfy the first property.
An intuitive theorem:
Let \(s^* = \limsup_{n \to \infty} s_n\) and \(t^* = \limsup_{n \to \infty} t_n\), as before. Suppose for the sake of contradiction \(t^* < s^*\). Choose \(x\) such that \(t^* < x < s^*\). Then by the second property of Theorem 1 there is an integer \(N_1\) such that \(n \geq N_1\) implies \(t_n < x\). Also by the first property of Theorem 1 there exists a subsequence \(\{s_{n_k}\}\) such that \(s_{n_k} \to s^*\). This implies that there exists an integer \(N_2\) such that \(n \geq N_2\) implies \(x < s_n\). But then for \(n \geq \max\{N_1, N_2\}\) we have \(t_n < x < s_n\). This gives us our required contradiction.
A similar argument can be made for the \(\liminf\) case.
Next we give a necessary and sufficient condition for the convergence of a sequence in terms of its \(\liminf\) and \(\limsup\).
We divide the analysis into three cases.
First, let \(s \in \mathbb R\). Then if \(s^* = s_* = s\), Theorem 1 implies that for any \(\varepsilon > 0\) we have \(s_n \in (s-\varepsilon, s+\varepsilon)\) for all but finitely many \(n\), which means \(s_n \to s.\) On the other hand if \(s_n \to s\) then every subsequence \(\{s_{n_k}\}\) must converge to \(s\) and hence \(s^* = s_* = s\).
Now let \(s = +\infty\). Then \(s_n \to s\) means that for every \(M \in \mathbb R\) there is an integer \(N\) such that \(n \geq N\) implies \(s_n \geq M.\) This is same as saying \(s_* = +\infty\), which gives \(s^* = +\infty\) curtsy of Theorem 2.
Lastly, let \(s = -\infty\). Then \(s_n \to s\) means that for every \(M \in \mathbb R\) there is an integer \(N\) such that \(n \geq N\) implies \(s_n \leq M.\) This is same as saying \(s^* = -\infty,\) which gives \(s_* = -\infty\) curtsy of Theorem 2.
There is an equivalent and often useful way to express upper and lower limits.
We note that the sequence \(\{\sup_{k \ge n} s_k\}_{n \in \mathbb N}\) is monotonically decreasing and the sequence \(\{\inf_{k \ge n} s_k\}_{n \in \mathbb N}\) is monotonically increasing, and thus their limits exist in \(\overline{\mathbb R}.\)
We now show the equivalence of the two ways of looking at upper and lower limits.
We will prove the first equation. The proof for the second is similar. We prove the equation in two steps.
Let \(S = \{ s_n : n \in \mathbb N \}\). Let's show that \(\sup S = +\infty\) if and only if \(s^* = + \infty.\) Suppose first that \(\sup S = + \infty.\) Then we construct a subsequence \(\{s_{n_k}\}\) as follows. We let \(n_1 = 1.\) Suppose \(n_1, \ldots, n_{k}\) for some fixed \(k \ge 1\) have been chosen and let
Notice that \(S_k\) is infinite as otherwise we can find an \(M \in \mathbb R\) such that \(s_n \leq M\) for all \(n \geq 1\), contradicting the fact that \(\sup S = + \infty\). We pick \(n_{k+1}\) to be the smallest element of \(S_k\) which is bigger than \(n_k.\) The resulting subsequence satisfies the condition that \(s_{n_k} \geq k\) for \(k \geq 2\) and thus we conclude that \(s_{n_k} \to +\infty\) which gives \(s^* = +\infty.\) Now suppose that \(s^* = +\infty.\) From Theorem 1 we can conclude that there exists a subsequence \(\{s_{n_k}\}\) such that \(s_{n_k} \to +\infty.\) This immediately implies \(\sup S = +\infty.\)
For the second step, suppose \(\sup S < + \infty.\) Denote
These theorems make it easier to discover more properties of upper and lower limits.
If \(s^* = +\infty\) or \(t^* = +\infty\) or \(s^* = -\infty\) or \(t^* = -\infty\), it is easily checked that the inequality is true, and so we may assume \(s^*, t^* \in \mathbb R.\)
For two sets \(S\) and \(T\) of real numbers satisfying \(S \subseteq T\), we know that \(\sup S \le \sup T\). This fact along with the observation