Upper and Lower Limits

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:

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

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.

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.