Aditya Makkar
Upper and Lower Limits
  1. Introduction
  2. Definitions
  3. Some Useful Lemmas
  4. Properties
  5. Upper and Lower Limits — A Reprise
  6. More Properties

Most of what follows is taken from Rudin's book Principles of Mathematical Analysis.

Introduction

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

\[\begin{aligned} \limsup_{n \to \infty} \frac{|f(n)|}{g(n)} < \infty.\end{aligned}\]

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.

Definitions

I start with some definitions.

Definition 1: A sequence is a real-valued function defined on the set \(\mathbb N\) of positive integers. If \(f(n) = x_n\), for \(n \in \mathbb N\), we denote the sequence \(f\) by the symbol \(\{x_n\}_{n \in \mathbb N}\), or simply \(\{x_n\}\), or sometimes by \(x_1, x_2, \ldots\).
Definition 2: A sequence \(\{p_n\}\) in a metric space \((X, d)\) is said to converge if there is a point \(p \in X\) with the following property: for every \(\varepsilon > 0\) there is an integer \(N\) such that \(n \geq N\) implies that \(d(p_n, p) < \varepsilon\). We write this as \(\lim_{n \to \infty} p_n = p\) or simply as \(p_n \to p\).
Definition 3: Let \(\{s_n\}\) be a sequence of real numbers with the following property: For every real \(M\) there is an integer \(N\) such that \(n \geq N\) implies \(s_n \geq M\). We then write \(s_n \to +\infty\). Similarly for \(s_n \to -\infty\).

Note: The symbol \(\to\) is now used for certain type of divergent sequences as well.

Definition 4: Given a sequence \(\{p_n\}\), consider a sequence \(\{n_k\}\) of positive integers, such that \(n_1 < n_2 < \cdots\). Then the sequence \(\{p_{n_k}\}_{k \in \mathbb N}\), which is a composition of the functions \(\{n_k\}_k\) and \(\{p_n\}_n\), is called a subsequence of the sequence \(\{p_n\}\). If \(\{p_{n_k}\}\) converges, its limit is called a subsequential limit of \(\{p_n\}\).
Definition 5: Let \(\{s_n\}\) be a sequence of real numbers. Let \(E\) be the set of numbers \(x\) (in the extended real number system, i.e., \(x \in \overline{\mathbb R} := \mathbb R \cup \{+\infty, -\infty\}\)) such that \(s_{n_k} \to x\) for some subsequence \(\{s_{n_k}\}\). Therefore, this set contains all the subsequential limits of \(\{s_n\}\) plus possibly the numbers \(+\infty\) and \(-\infty\). We define
\[\begin{aligned} s^* &= \sup E \\ s_* &= \inf E. \end{aligned}\]
The numbers \(s^*\) and \(s_*\) are called the upper and lower limits of \(\{s_n\}\) respectively. We use the notation
\[\begin{aligned} \limsup_{n \to \infty} s_n &= s^* \\ \liminf_{n \to \infty} s_n &= s_*. \end{aligned}\]

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\).

Some Useful Lemmas

Now let us prove some lemmas that will be useful later.

Lemma 1: The subsequential limits of a sequence \(\{p_n\}\) in a metric space \(X\) form a closed subset of \(X\).

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

\[\begin{aligned} d(q, p_{n_i}) \leq d(q, x) + d(x, p_{n_i}) < \frac{\delta}{2^{i-1}} \quad \text{for } i = 1,2,\ldots.\end{aligned}\]
This implies \(p_{n_k} \to q\), showing \(q \in E\).

Lemma 2: Let \(F\) be a nonempty closed set of real numbers which is bounded above. Let \(\alpha = \sup F\). Then \(\alpha \in F\).
Assume for the sake of the contradiction that \(\alpha \notin F\). Then since \(F^\mathsf{c}\) is an open set (because \(F\) is closed) there exists an \(\varepsilon > 0\) such that \((\alpha - \varepsilon, \alpha + \varepsilon) \subset F^\mathsf{c}\). But this implies \(\alpha - \frac{\varepsilon}{2}\) is an upper bound for \(F\) which is smaller than \(\alpha\). This gives us our required contradiction.

Properties

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:

  1. \(s^* \in E\), and

  2. 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.

  1. We divide it into three cases depending on what value \(s^*\) takes:

    1. 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\).

    2. 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.\)

    3. Lastly, if \(s^* = -\infty\), then \(E\) contains only one element, namely \(-\infty\), and there is no subsequential limit. Thus, \(s^* \in E\).

  2. 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:

Theorem 2: If for two sequences \(\{s_n\}\) and \(\{t_n\}\) we have \(s_n \leq t_n\) for \(n \geq N\), where \(N \in \mathbb N\) is fixed, then
\[\begin{aligned} \liminf_{n \to \infty} s_n &\le \liminf_{n \to \infty} t_n \\ \limsup_{n \to \infty} s_n &\le \limsup_{n \to \infty} t_n. \end{aligned}\]

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\).

Theorem 3: For a real-valued sequence \(\{s_n\}\), \(s_n \to s \in \overline{\mathbb R}\) if and only if
\[\begin{aligned} \limsup_{n \to \infty} s_n = \liminf_{n \to \infty} s_n = s.\end{aligned}\]

We divide the analysis into three cases.

  1. 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\).

  2. 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.

  3. 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.

Upper and Lower Limits — A Reprise

There is an equivalent and often useful way to express upper and lower limits.

Definition 6: Let \(\{s_n\}\) be a sequence of real numbers. We define the notation
\[\begin{aligned} \sup_{k \ge n} s_k &:= \sup \{s_k : k \ge n\} \\ \inf_{k \ge n} s_k &:= \inf \{s_k : k \ge n\}. \end{aligned}\]

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.

Theorem 4: Let \(\{s_n\}\) be a sequence of real numbers. Then
\[\begin{aligned} \lim_{n \to \infty} \sup_{k \ge n} s_k &= \limsup_{n \to \infty} s_n, \\ \lim_{n \to \infty} \inf_{k \ge n} s_k &= \liminf_{n \to \infty} s_n. \end{aligned}\]

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

\[\begin{aligned} S_k = \{ n \in \mathbb N : s_n \geq \max\{s_{n_1}, \ldots, s_{n_k}, k\} + 1 \}.\end{aligned}\]

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

\[\begin{aligned} a_n = \sup_{k \ge n} s_k.\end{aligned}\]
Notice that \(a_1 < +\infty\) and \(\{a_n\}\) is a monotonically decreasing sequence. Therefore, we have that either \(\{a_n\}\) is lower bounded, in which case it converges to, say, \(a,\) or it is not, in which case \(a_n \to -\infty.\) Since \(s_n \leq a_n,\) by Theorem 2 we can conclude
\[\begin{aligned} s^* \le a^* = \lim_{n \to \infty} a_n,\end{aligned}\]
where the last equality follows from Theorem 3. We will now show that
\[\begin{aligned} s^* \ge \lim_{n \to \infty} a_n,\end{aligned}\]
which will give us our required equality. If \(\lim_{n \to \infty} a_n = -\infty\), there is nothing to prove and so we assume that \(a > -\infty.\) Let \(\varepsilon > 0\) be given and define
\[\begin{aligned} B := \{ n \in \mathbb N : s_n \ge a - \varepsilon \}.\end{aligned}\]
We claim that \(B\) is infinite. Indeed, if \(B\) were finite we could find \(N \in \mathbb N\) so that \(N \geq \max B.\) This will imply that \(s_n \le a - \varepsilon\) for all \(n \geq N\) and so \(a_n \leq a - \varepsilon\) for \(n \geq N.\) But then by Theorem 2 we would conclude \(a = \lim a_n \leq a-\varepsilon.\) Thus \(B\) is infinite and we let \(\{s_{n_k}\}\) be a subsequence of \(\{s_n\}\) with \(n_k \in B.\) Notice that \(\limsup_{k \to \infty} s_{n_k} \leq s^*,\) since any subsequential limit of \(\{s_{n_k}\}\) is also a subsequential limit of \(\{s_n\}.\) This along with Theorem 2 give
\[\begin{aligned} a - \varepsilon \le \limsup_{k \to \infty} s_{n_k} \leq s^*.\end{aligned}\]
Since \(\varepsilon\) was arbitrary we conclude that \(s^* \ge a\), which is what we wanted.

More Properties

These theorems make it easier to discover more properties of upper and lower limits.

Theorem 5: Let \(\{s_n\}\) be a sequence of real numbers. Then
\[\begin{aligned} \liminf_{n \to \infty} s_n = - \limsup_{n \to \infty} (-s_n).\end{aligned}\]
If for a set \(S\) of real numbers, we denote by \(-S\) the set \(\{-s : s \in S\},\) then the theorem follows immediately from the simple observation that
\[\begin{aligned} \inf S = - \sup (-S)\end{aligned}\]
and Theorem 4.
Theorem 6 [Subadditivity of \(\limsup\)]: For any two real sequences \(\{s_n\}\) and \(\{t_n\}\), we have
\[\begin{aligned} \limsup_{n \to \infty} (s_n + t_n) \le \limsup_{n \to \infty} s_n + \limsup_{n \to \infty} t_n,\end{aligned}\]
provided the sum on the right is not of the form \(\infty - \infty.\)

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

\[\begin{aligned} \{(k,k) : k \ge n\} \subseteq \{k : k \ge n\} \times \{k : k \ge n\}\end{aligned}\]
for any \(n \in \mathbb N\), imply
\[\begin{aligned} \sup_{k \ge n} (s_k + t_k) \le \sup_{k \ge n} s_k + \sup_{k \ge n} t_k.\end{aligned}\]
Taking limit as \(n \to \infty\) now gives us our desired inequality.

Theorem 7 [Superadditivity of \(\liminf\)]: For any two real sequences \(\{s_n\}\) and \(\{t_n\}\), we have
\[\begin{aligned} \liminf_{n \to \infty} (s_n + t_n) \ge \liminf_{n \to \infty} s_n + \liminf_{n \to \infty} t_n.\end{aligned}\]
Similar to the proof of Theorem 6.

Back to top