Theorem 4. Let \((a_n), (b_n)\) and \((c_n)\) be sequences.
i) If \(a_n \to a, b_n \to b\), and for all indices \(n: a_n \le b_n\), then we have \(a \le b\).
ii) (Squeeze Theorem)
If \(a_n \to a, b_n \to a\), and for all indices \(n\):
\(a_n \le c_n \le b_n\), then \(c_n \to a\).
iii) If for all indices \(n: |a_n - a| \le b_n\), and \(b_n \to 0\), then \(a_n \to a\).
iv) If \((b_n)\) is bounded and \(a_n \to 0\), then \(a_n b_n \to 0\).
Proof. W.l.o.g. we assume that all sequences start at \(n=1\).
i) We prove this part by contradiction.
Assume: \(a > b\). We set \(\epsilon := \frac{a-b}{2} > 0\).
\(a_n \to a \implies \exists N_1 \in \mathbb{N} \quad \forall n \ge N_1 : a_n \in U_\epsilon(a)\)
\(b_n \to b \implies \exists N_2 \in \mathbb{N} \quad \forall n \ge N_2 : b_n \in U_\epsilon(b)\)
\(\implies \forall n \ge \max\{N_1, N_2\}:\)
\(a_n > a-\epsilon = \frac{a+b}{2} = b+\epsilon > b_n\), which is a contrad.
ii) \(a_n \to a\) and \(b_n \to a \implies \exists N \in \mathbb{N} \quad \forall n \ge N :\)
\(|a_n - a| < \frac{\epsilon}{2}\) and \(|b_n - a| < \frac{\epsilon}{2}\)
for any given \(\epsilon > 0\).
\(\implies \forall n \ge N : \quad a_n - a \le c_n - a \le b_n - a\)
\(\implies \forall n \ge N : |c_n - a| \le \max\{|a_n-a|, |b_n-a|\}\)
\(\le |a_n - a| + |b_n - a| < \frac{\epsilon}{2} + \frac{\epsilon}{2}=\epsilon\).
iii) follows directly from the definition of convergence.
iv) Let \(\epsilon > 0\). We know \((b_n)\) is bounded
\(\implies \exists M > 0 \quad \forall n \ge 1 : |b_n| \le M\).
As \((a_n)\) converges to 0, we know
\(\exists N \in \mathbb{N} \quad \forall n \ge N : |a_n| < \frac{\epsilon}{M}\).
\(\implies \forall n \ge N : |a_n b_n| \le M |a_n| < M \frac{\epsilon}{M}=\epsilon\).
Examples. i) We have \(\frac{n-1}{n+1} = \frac{1-\frac{1}{n}}{1+\frac{1}{n}} \to \frac{1}{1} = 1\),
where we use Thm 3, iv).
ii) Let \(\alpha > 0\) be a fixed positive number and \(a_n := \frac{1}{n^\alpha}, n \in \mathbb{N}\). We show \(a_n \to 0\).
Let \(\epsilon > 0\), and let us choose \(N > \frac{1}{\epsilon^{1/\alpha}}\).
Then we have for all \(n \ge N\) :
\(|\frac{1}{n^\alpha}| = \frac{1}{n^\alpha} \le \frac{1}{N^\alpha} < \epsilon\).
iii) We show \(\lim_{n \to \infty} \sqrt[n]{n} = 1\).
We recall the binomial theorem
\((x+y)^n = \sum_{k=0}^n \binom{n}{k} x^k y^{n-k}\)
and define \(a_n := \sqrt[n]{n} - 1, n \in \mathbb{N}\).
\(\implies \forall n \ge 1 : a_n \ge 0\).
\(\implies \forall n \ge 2 : n = (\sqrt[n]{n})^n = (a_n+1)^n\)
\(= \sum_{k=0}^n \binom{n}{k} (a_n)^k \ge 1 + \binom{n}{1} a_n + \binom{n}{2} (a_n)^2\)
\(\ge \binom{n}{2} (a_n)^2 = \frac{n(n-1)}{2} (a_n)^2\)
\(\implies \forall n \ge 2 : (a_n)^2 \le \frac{2}{n-1}\)
\(\implies \forall n \ge 2 : |a_n| \le \sqrt{\frac{2}{n-1}} \to 0\) (c.f. example ii)
\(\implies a_n \to 0\) (here we use Thm 4, iii).
iv) For fixed \(a > 0\) we have \(\lim_{n \to \infty} \sqrt[n]{a} = 1\).
Case 1: \(a \ge 1: \forall n \ge a : 1 \le \sqrt[n]{a} \le \sqrt[n]{n}\)
\(\implies\) (Squeeze Thm) \(\sqrt[n]{a} \to 1\).
Case 2: \(0 < a < 1 : \frac{1}{a}> 1 \implies \sqrt[n]{\frac{1}{a}} \to 1\) (Case 1)
\(\implies \sqrt[n]{a} = \frac{1}{\sqrt[n]{1/a}} \to 1\), by Thm 3, iv).
v) For fixed \(x \in \mathbb{R}\) with \(|x| < 1\) we have \(x^n \to 0\),
and more generally, for fixed \(k \in \mathbb{N}_0\) we have \(n^k x^n \to 0\).
Let \(\epsilon > 0\). We have \(|n^k x^n| = n^k |x|^n < \epsilon\)
\(\iff |x| < \frac{\epsilon^{1/n}}{(n^{1/n})^k}=\frac{\epsilon^{1/n}}{(\sqrt[n]{n})^k}\)
We know \(\lim_{n \to \infty} \epsilon^{1/n} = \lim_{n \to \infty} (\sqrt[n]{n})^k = 1\),
\(\implies \exists N \in \mathbb{N} \quad \forall n \ge N : \frac{\epsilon^{1/n}}{(\sqrt[n]{n})^k} > |x|\).
vi) For fixed \(x \in \mathbb{R}\) with \(|x| < 1\) we have
\(\lim_{n \to \infty} \sum_{k=0}^n x^k = \frac{1}{1-x}\) :
\(|\sum_{k=0}^n x^k - \frac{1}{1-x}| = |\frac{1-x^{n+1}}{1-x} - \frac{1}{1-x}| = \frac{|x|}{1-x} |x|^n \to 0\),
where we use example iv).
So far, we could only prove convergence of a sequence if we knew the potential limit a priori. In the following, we will look at principles that allow us to prove convergence without prior knowledge of the limit.
Definition. A sequence \((a_n)\) is called
i) increasing if \(a_n \le a_{n+1}\)
ii) strictly increasing if \(a_n < a_{n+1}\)
iii) decreasing if \(a_n \ge a_{n+1}\)
iv) strictly decreasing if \(a_n > a_{n+1}\)
for all its indices \(n\).
A sequence that is increasing or decreasing is called monotonic.
Definition. Let \((a_n)_{n=1}^\infty\) be a sequence and let \((n_k)_{k=1}^\infty\) be a strictly increasing sequence of natural numbers, i.e., \(n_k < n_{k+1}\) for all \(k \in \mathbb{N}\) and \(n_k \in \mathbb{N}\). Then \((a_{n_k})_{k=1}^\infty=(a_{n_1}, a_{n_2}, \dots)\) is called a subsequence of \((a_n)_{n=1}^\infty\).
More generally, if \((a_n)\) starts with an index \(l \in \mathbb{Z}\), and \((n_k)_{k=1}^\infty\) is a strictly increasing sequence with \(n_1 \ge l\), then \((a_{n_k})_{k=1}^\infty\) is a subsequence of \((a_n)\).
Example. Let \((a_n)_{n=1}^\infty\) be defined by \(a_n = \frac{1}{n}\) and \((n_k)_{k=1}^\infty\) by \(n_k = k^2\), then the subsequence \((a_{n_k})_{k=1}^\infty\) is given by \(a_{n_k} = \frac{1}{k^2}\).
Theorem 5. Every sequence in \(\mathbb{R}\) has a monotonic subsequence.
Proof. Let us consider a sequence \((a_n)_{n=1}^\infty\).
An index \(m \in \mathbb{N}\) of the sequence is called a peak if for all \(n > m\) we have \(a_n < a_m\).
Case 1 There are infinitely many peaks: \(m_1 < m_2 < \dots\)
Then \((a_{m_k})_{k=1}^\infty\) is a strictly decreasing subsequence of \((a_n)\).
Diagram (Case 1): infinitely many peaks selected as \(m_1,m_2,m_3,\dots\)
Blue highlighted peaks define the strictly decreasing subsequence \((a_{m_k})\).
subsequence of \((a_n)\).
Case 2 There are only finitely many peaks.
\(\implies \exists n_1 \in \mathbb{N}\) such that \(n_1\) is greater than all peaks
\(\implies \exists n_2 > n_1\) such that \(a_{n_2} \ge a_{n_1}\).
Diagram (Case 2): after the last peak, one can keep choosing \(n_{k+1} > n_k\) with \(a_{n_{k+1}} \ge a_{n_k}\)
Green points are chosen inductively after the last peak, giving an increasing subsequence \((a_{n_k})\).
We can proceed inductively to find a strictly increasing sequence \((n_k)_{k=1}^\infty\) of natural numbers such that \((a_{n_k})_{k=1}^\infty\) is an increasing subsequence.
Definition. For a sequence of real numbers \((a_n)_{n=k}^\infty\) that is bounded above, we define
\(\sup_{n \ge k} a_n := \sup \{ a_n : n \ge k \}\),
which is the least upper bound of \((a_n)_{n=k}^\infty\).
Likewise, for a sequence of real numbers \((a_n)_{n=k}^\infty\) that is bounded below, we define
\(\inf_{n \ge k} a_n := \inf \{ a_n : n \ge k \}\),
which is the greatest lower bound of \((a_n)_{n=k}^\infty\).
Example For the sequence \(a_n := \frac{1}{n}, n \ge 1\), we have
\(\inf_{n \ge 1} a_n = 0\) and \(\sup_{n \ge 1} a_n = a_1 = 1\).
Theorem 6. (Monotone Convergence Theorem)
Every bounded monotonic sequence is convergent.
More precisely, if \((a_n)_{n=k}^\infty\) is a bounded increasing sequence, then \(\lim_{n \to \infty} a_n = \sup_{n \ge k} a_n\).
Likewise, if \((a_n)_{n=k}^\infty\) is a bounded decreasing sequence, then \(\lim_{n \to \infty} a_n = \inf_{n \ge k} a_n\).
Proof. W.l.o.g. we only prove the statement in the case of a bounded increasing sequence \((a_n)_{n=1}^\infty\), and we set \(A := \sup_{n \ge 1} a_n\).
We know \(\forall n \ge 1 : a_n \le A\) and
\(\forall \epsilon > 0 \quad \exists N \in \mathbb{N} : A-\epsilon < a_N\) (\(A\) is the smallest upper bound for \(a_n\)).
\(\implies (a_n \text{ is increasing}) \quad \forall \epsilon > 0 \quad \exists N \in \mathbb{N} \quad \forall n \ge N : A-\epsilon < a_n\)
\(\implies \forall \epsilon > 0 \quad \exists N \in \mathbb{N} \quad \forall n \ge N : |A-a_n| = A-a_n < \epsilon\).
\(\implies \lim_{n \to \infty} a_n = A\).
Examples. i) The famous "Basel problem" asks for the value of the limit \(\lim_{n \to \infty} \sum_{k=1}^n \frac{1}{k^2}\) (\(=\frac{\pi^2}{6}\), Euler 1734).
We cannot solve this problem yet, but we can understand that the limit exists: