Monotone sequences and Cauchy sequences

 Deciding whether a given sequence \(\{a_n\}\) converges or diverges is usually very difficult. Sometimes it is possible to decide if a sequence converges without knowing its limit explicitly if certain conditions are met.

Definition (Monotone increasing/decreasing sequences)

Let \(\{a_n\}\) be a sequence. If

\[a_1 \leq a_2 \leq a_3 \leq \cdots \leq a_n \leq a_{n+1} \leq \cdots\]

holds, that is, 

\[\forall n\in\mathbb{N} ~ (a_n \leq a_{n+1}),\]

then \(\{a_n\}\) is said to be monotone increasing.

If

\[a_1 \geq a_2 \geq a_3 \geq \cdots \geq a_n \geq a_{n+1} \geq \cdots\]

hold, that is,

\[\forall n\in\mathbb{N} ~ (a_n \geq a_{n+1}),\]

then \(\{a_n\}\) is said to be monotone decreasing.

If a sequence is either monotone increasing or monotone decreasing, we may simply say it is monotone.

Example. Let us define the sequence \(\{a_n\}\) by

\[ \begin{eqnarray} a_1 &=& 2,\\ a_{n+1} &=& \frac{1}{2}\left(a_n + \frac{2}{a_n}\right), ~ n = 1, 2, \cdots. \end{eqnarray} \]

It can be shown (exercise!) that this sequence has the following properties:

1. \(\forall n\in\mathbb{N} ~ (a_n \geq \sqrt{2})\).
2. \(\{a_n\}\) is monotone decreasing.
3. \(\lim_{n\to\infty}a_n = \sqrt{2}\).

Here are the first few terms.

\[ \begin{eqnarray} a_1 &=& 2,\\ a_2 &=& = \frac{1}{2}(a_1 + \frac{2}{a_1}) = \frac{3}{2} = 1.5,\\ a_3 &=& = \frac{1}{2}(a_2 + \frac{2}{a_2}) = \frac{17}{12} = 1.41666666\cdots,\\ a_4 &=& \frac{1}{2}(a_3 + \frac{2}{a_3}) = \frac{577}{408} = 1.41421568\cdots,\\ a_5 &=& \frac{1}{2}(a_4 + \frac{2}{a_4}) = \frac{665857}{470832} = 1.41421356\cdots \end{eqnarray} \]

This sequence is monotone decreasing but it cannot be arbitrarily small because it is also bounded below. Therefore it must converge to some number (namely \(\sqrt{2}\) in this case). That such a real number exists is guaranteed by the continuity of real numbers. □

The observation in the above example can be generalized.

Theorem (Monotone convergence theorem)

Any bounded monotone sequence converges.

Proof. Suppose \(\{a_n\}\) is a bounded monotone increasing sequence. Then the set \(S = \{a_n\mid n\in\mathbb{N}\}\) is bounded above so that its supremum \(\alpha\) exists. For any \(\varepsilon > 0\), \(\alpha - \varepsilon\) is not an upper bound of \(S\) so there exists \(N\in\mathbb{N}\) such that \(\alpha - \varepsilon < a_N\). Since \(\{a_n\}\) is monotone increasing, for all \(n\geq N\), \(a_n \geq a_N > \alpha - \varepsilon\). Since \(\alpha\) is the supremum of \(\{a_n\}\), we have \(a_n \leq \alpha < \alpha + \varepsilon\). Thus we have \(\alpha -\varepsilon < a_n < \alpha + \varepsilon\) or \(|a_n -\alpha| < \varepsilon\) for all \(n\geq N\). Hence \(\lim_{n\to\infty}a_n = \alpha\).

We can prove similarly for the case of a bounded monotone decreasing sequence. ■

Definition (Cauchy sequence)

The sequence \(\{a_n\}\) is said to be a Cauchy sequence if and only if the following condition is met.

• For any \(\varepsilon > 0\), there exists \(N\in\mathbb{N}\) such that for any \(k, l\geq N\), \(|a_k - a_l| < \varepsilon\).

Or, in a logical form,

\[\forall \varepsilon > 0, \exists N\in\mathbb{N}, \forall k,l\in\mathbb{N} ~ (k, l \geq N \implies |a_k - a_l| < \varepsilon).\]

Theorem

Any convergent sequence is a Cauchy sequence.

Proof. Suppose \(\lim_{n\to\infty}a_n = \alpha\). For any \(\varepsilon > 0\), there exists \(N\in\mathbb{N}\) such that for all \(k,l \geq N\),

\[|a_k - \alpha| < \varepsilon, ~|a_l - \alpha| < \varepsilon.\]

Thus,

\[|a_k - a_l| = |(a_k - \alpha) + (\alpha - a_l)| \leq |a_k - \alpha| + |\alpha - a_l| < \varepsilon + \varepsilon = 2\varepsilon.\]

\(2\varepsilon\) is an arbitrary positive real number. Therefore, \(\{a_n\}\) is a Cauchy sequence. ■

The converse is also true, but the proof is beyond the scope of this lecture.

Theorem

Any Cauchy sequence converges. 

Corollary

A sequence converges if and only if it is a Cauchy sequence.

For later convenience, we provide the following theorem without proof.

Theorem (Bolzano-Weierstrass Theorem)

Let \(\{a_n\}\) be a sequence such that \(a_n \in [c, d]\) for all \(n\in\mathbb{N}\). Then there exists a subsequence \(\{a_{n_k}\}\) of \(\{a_n\}\) that converges to a value in the closed interval \([c,d]\).

Proof. Exercise. (Hint: use the squeeze theorem) ■