Table of Contents

Cauchy Sequences and Convergence

Recall: For a bounded sequence \((a_n)\):

  • \(I_N = \inf\{a_n, n>N\}\)
  • \(S_N = \sup\{a_n, n>N\}\)
  • \(I_1 \leq I_2 \leq ... \leq \liminf a_n \leq \limsup a_n \leq ... \leq S_2 \leq S_1\)

Def: \((a_n)\) is Cauchy if for all \(\epsilon > 0\) we can find an such that \(\vert a_n - a_m \vert < \epsilon\), for all \(n,m > N\)

Thm: A convergent sequence \((a_n)\) implies that \((a_n)\) is Cauchy

Proof: \(\forall \epsilon > 0\) s.t. \(\vert a_n - a_m \vert < \epsilon \forall n,m > N\) \(\implies a_n < a_m + \epsilon \forall n,m > N\)

For any \(n>N\), we have

  • \(a_n < a_m + \epsilon\ \forall m > N\)
  • \(\implies a_n \leq \inf\{a_m: m > N\} + \epsilon\)

So we have, for any \(n > N\),

  • \(a_n \leq I_N + \epsilon\)
  • \(\implies \sup\{a_n: n > N\} \leq I_N + \epsilon\)
  • \(\limsup_{n \to \infty} a_n \leq S_N \leq I_N + \epsilon \leq \liminf_{n \to \infty} a_n+ \epsilon\)
  • \(\implies \limsup a_n \leq \liminf a_n + \epsilon \forall \epsilon > 0\)
  • \(\implies \limsup a_n \leq \liminf a_n\), since we always have \(\liminf a_n \leq \limsup a_n < n\)

We proved that bounded and \(\liminf = \limsup\) implies convergence, and convergence implies Cauchy, so now we will prove Cauchy implies \(\liminf = \limsup\).

Cauchy Implies Infimum = Supremum

Def: A subsequence of a sequence \((a_n)\) is a sequence \((a_{k_n}) = (a_{k_1}, a_{k_2}, ...)\) where \(1 \leq k_1 < k_2 < ... < a_m\) are positive integers, e.g.

  • \((a_{2n}) = (a_2, a_4, a_6, ...)\)
  • \((a_{2n-1}) = (a_1, a_3, a_5, ...)\)

In homework, we proved that \(\lim_{n \to \infty} a_n = 0 \implies \lim_{n \to \infty} a_{2n} = a = \lim_{n \to \infty} a_{2n-1}\)

Subsequences Approach Sequence Limit

Question: Suppose \(\lim_{n \to \infty} a_n = a\), is it true that \(\lim_{n \to \infty} a_{k_n} = a\) for any subsequence \((a_{k_n})\)?

Yes: \(\forall \epsilon > 0, \exists N > 0\) s.t. \(\vert a_n - a \vert < \epsilon \forall n > N\)

The intuition is that there exists a \(k_n\) that is greater than \(N\), at which point the bounds will hold true.

And our sequence is \(a_{k_1}, ...\), which contains strictly increasing \(k_n\), so \(\exists M > 0\) such that \(k_M > N\). Then, for any \(n > M\), we know \(\vert a_{k_n} - a \vert < \epsilon\) since \(k_n > k_M > N\).

The converse is not true. Consider \((0, 1, 0, 1, ...)\). The odd terms converge to \(0\), but the even terms to \(1\). Note that \(\liminf a_n = 0\) and \(\limsup a_n = 1\). We will prove that for any bounded sequence, there exists a subsequence that converges to \(\liminf\) and one that converges to \(\limsup\).

Another question: If \(\lim a_{2n} = a = \lim a_{2n - 1}\), does this imply that \(\lim a_n = a\)? It turns out the answer is yes, and the proof is left as an exercise.

Bolzano Weierstrass

Definition: Any bounded sequence has a convergent subsequence

It suffices to prove any bounded sequence has a monotone subsequence. If we can bound this monotone subsequence, it will be monotone and bounded, hence convergent.

Lemma: Any bounded subsequence has a monotone subsequence.

Proof:

Definition: Given a bounded sequence \((a_n)\), we say \(a_n\) is big if it is bigger than all the terms after it, i.e. \(a_n > a_m \forall n < m\).

For any bounded sequence \((a_n)\),

  1. It has infinitely many big terms, or
  2. It has finitely many big terms.

In the first case, the sequence has infinitely many big terms, so we can just take all the big terms: \(\{ a_{k_1}, a_{k_2}, ...\}\), the sequence of big terms from \((a_n)\). This gives a subsequence of \((a_n)\), a strictly decreasing subsequence (since each term is strictly greater than the term after).

In the second case, the sequence has finitely many big terms, so we take \(N = \max\{k_1, ... k_n\}\). Consider only \(a_n\) for \(n>N\). These \(a_n\) are not big for all of these \(n\)s.
Now we define \(a_{k_1} = a_{N+1}\). Since \(k_1 = N+1 > N\), \(a_k\) is not big. This implies that there exists \(k_2 > k_1\) such that \(a_{k_2} \geq a_{k_1}\). Since \(k_2 > k_1 > N\), \(a_{k_2}\) is not big. Using the same argument, we can construct \(k_3\), and construct the remaining inductively. This creates a monotonically increasing subsequence.

Bounded to Limsup and Liminf

Theorem: For a bounded sequence, there exists two subsequences that converges to \(\liminf\) and \(\limsup\), respectively.

To prove this theorem, first we prove a lemma:

Lemma: Subsequence iff Infinite Set Within Neighborhood

Lemma: Having a subsequence of a sequence converging to \(a\) is equivalent to \(\forall \epsilon > 0\), the set \(\{n \in N: \vert a_n - a \vert < \epsilon\}\) is infinite.

Proof:

(→): \((a_{k_n})\) converges to \(a\):

\(\forall \epsilon > 0, \exists N > 0\) s.t. \(\vert a_{k_n} - a \vert < \epsilon \forall n > N\)

which implies that \(\{k_{N+1}, k_{N+2}, ...\} \subset \{n \in N: \vert a_n - a \vert < \epsilon\}\)

(←):
Idea: We’ll find a subsequence (\(a_{k_1}, a_{k_2}, ...\)) such that the differences are less than 1, \(1/2\), … \(1/n\).

  • We know that \(\{n \in N: \vert a_n - a \vert < 1\}\) is infinite.
  • We know that \(\{n \in N: \vert a_n - a \vert < 1/2\}\) is infinite, so \(\exists k_2 > k_1\) s.t. \(\vert a_{k_2} - a \vert < 1/2\).
  • We know that \(\{n \in N: \vert a_n - a \vert < 1/3\}\) is infinite, so \(\exists k_3 > k_1\) s.t. \(\vert a_{k_3} - a \vert < 1/3\).
  • etc.

Now back to the original proof:

Proof:

Let \(Z := \limsup_{n\to\infty} a_n = \lim_{N\to\infty} S_N = \limsup_{N\to\infty} \{a_n : n > N\}\)
Want to show: \(\forall \epsilon > 0\), the set \(\{n \in N: \vert a_n - z \vert < \epsilon\}\) is infinite.

Proof by contradiction. Suppose that \(\{n \in N: \vert a_n - z \vert < \epsilon\}\) is finite.

  1. \(\exists N_1 > 0\) such that \(z - \epsilon < \sup \{a_n: n>N\} = S_{N_1} < z-\epsilon\). This implies that \(a_n < z + \epsilon\) for all \(n > N_1\).
  2. Having a finite set means that \(\exists N_2 > 0\) such that \(z - \epsilon < a_n < z + \epsilon\) is false \(\forall n > N_2\).

Now let \(N := \max\{N_1, N_2\}\). For any \(n > N\), we have

  1. \(a_n < z + \epsilon\)
  2. \(z - \epsilon < a_n < z + \epsilon\) is false.

which implies that \(\forall n > N, a_n \leq z - \epsilon\), which means \(\sup\{a_n: n > N\} \leq z - \epsilon\). But recall that \(\sup\{a_n: n > N\} = S_N = \limsup_{n\to\infty}a_n = z\), which is a contradiction.