RA Cauchy sequences

Section 2.4 Cauchy sequences

Note: less than a lecture

Often we wish to describe a certain number by a sequence that converges to it. In this case, it is impossible to use the number itself in the proof that the sequence converges. It would be nice if we could check for convergence without knowing the limit.

Definition 2.4.1.

A sequence \(\{ x_n \}_{n=1}^\infty\) is a Cauchy sequence¹ if for every \(\epsilon > 0\) there exists an \(M \in \N\) such that for all \(n \geq M\) and all \(k \geq M\text{,}\) we have

\begin{equation*} \abs{x_n - x_k} < \epsilon . \end{equation*}

Informally, being Cauchy means that the terms of the sequence are eventually all arbitrarily close to each other. We might expect such a sequence to be convergent, and we would be correct due to \(\R\) having the least-upper-bound property. Before we prove this fact, we look at some examples.

Example 2.4.2.

The sequence \(\{ \nicefrac{1}{n} \}_{n=1}^\infty\) is a Cauchy sequence.

Proof: Given \(\epsilon > 0\text{,}\) find \(M\) such that \(M > \nicefrac{2}{\epsilon}\text{.}\) Then for \(n,k \geq M\text{,}\) we have \(\nicefrac{1}{n} < \nicefrac{\epsilon}{2}\) and \(\nicefrac{1}{k} < \nicefrac{\epsilon}{2}\text{.}\) Therefore, for \(n, k \geq M\text{,}\) we have

\begin{equation*} \abs{\frac{1}{n} - \frac{1}{k}} \leq \abs{\frac{1}{n}} + \abs{\frac{1}{k}} < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon. \end{equation*}

Example 2.4.3.

The sequence \(\bigl\{ {(-1)}^n \bigr\}_{n=1}^\infty\) is not a Cauchy sequence.

Proof: Given any \(M \in \N\text{,}\) take \(n \geq M\) to be any even number, and let \(k \coloneqq n+1\text{.}\) Then

\begin{equation*} \begin{split} \abs{{(-1)}^n - {(-1)}^k} & = \abs{{(-1)}^n - {(-1)}^{n+1}} \\ & = \abs{1 - (-1)} = 2 . \end{split} \end{equation*}

Therefore, for any \(\epsilon \leq 2\) the definition cannot be satisfied, and the sequence is not Cauchy.

Proposition 2.4.4.

If a sequence is Cauchy, then it is bounded.

Proof.

Suppose \(\{ x_n \}_{n=1}^\infty\) is Cauchy. Pick an \(M\) such that for all \(n,k \geq M\text{,}\) we have \(\abs{x_n-x_k} < 1\text{.}\) In particular, for all \(n \geq M\text{,}\)

\begin{equation*} \abs{x_n - x_M} < 1 . \end{equation*}

By the reverse triangle inequality, \(\abs{x_n} - \abs{x_M} \leq \abs{x_n - x_M} < 1\text{.}\) Hence for \(n \geq M\text{,}\)

\begin{equation*} \abs{x_n} < 1 + \abs{x_M}. \end{equation*}

Let

\begin{equation*} B \coloneqq \max \bigl\{ \abs{x_1}, \abs{x_2}, \ldots, \abs{x_{M-1}}, 1+ \abs{x_M} \bigr\} . \end{equation*}

Then \(\abs{x_n} \leq B\) for all \(n \in \N\text{.}\)

Theorem 2.4.5.

A sequence of real numbers is Cauchy if and only if it converges.

Proof.

Suppose \(\{ x_n \}_{n=1}^\infty\) converges to \(x\text{,}\) and let \(\epsilon > 0\) be given. Then there exists an \(M\) such that for \(n \geq M\text{,}\)

\begin{equation*} \abs{x_n - x} < \frac{\epsilon}{2} . \end{equation*}

Hence for \(n \geq M\) and \(k \geq M\text{,}\)

\begin{equation*} \abs{x_n - x_k} = \abs{x_n - x + x - x_k} \leq \abs{x_n-x} + \abs{x-x_k} < \frac{\epsilon}{2} + \frac{\epsilon}{2} = \epsilon . \end{equation*}

Alright, that direction was easy. Now suppose \(\{ x_n \}_{n=1}^\infty\) is Cauchy. We have shown that \(\{ x_n \}_{n=1}^\infty\) is bounded. For a bounded sequence, liminf and limsup exist, and this is where we use the least-upper-bound property. If we show that

\begin{equation*} \liminf_{n\to \infty} x_n = \limsup_{n\to\infty} x_n , \end{equation*}

then \(\{ x_n \}_{n=1}^\infty\) must be convergent by Proposition 2.3.5.

Define \(a \coloneqq \limsup_{n\to\infty} x_n\) and \(b \coloneqq \liminf_{n\to\infty} x_n\text{.}\) By Theorem 2.3.4, there exist subsequences \(\{ x_{n_i} \}_{i=1}^\infty\) and \(\{ x_{m_i} \}_{i=1}^\infty\text{,}\) such that

\begin{equation*} \lim_{i\to\infty} x_{n_i} = a \qquad \text{and} \qquad \lim_{i\to\infty} x_{m_i} = b. \end{equation*}

Given an \(\epsilon > 0\text{,}\) there exists an \(M_1\) such that \(\abs{x_{n_i} - a} < \nicefrac{\epsilon}{3}\) for all \(i \geq M_1\) and an \(M_2\) such that \(\abs{x_{m_i} - b} < \nicefrac{\epsilon}{3}\) for all \(i \geq M_2\text{.}\) There also exists an \(M_3\) such that \(\abs{x_n-x_k} < \nicefrac{\epsilon}{3}\) for all \(n,k \geq M_3\text{.}\) Let \(M \coloneqq \max \{ M_1, M_2, M_3 \}\text{.}\) If \(i \geq M\text{,}\) then \(n_i \geq M\) and \(m_i \geq M\text{.}\) Hence,

\begin{equation*} \begin{split} \abs{a-b} & = \abs{a-x_{n_i}+x_{n_i} -x_{m_i}+x_{m_i} -b} \\ & \leq \abs{a-x_{n_i}} + \abs{x_{n_i} -x_{m_i}} + \abs{x_{m_i} -b} \\ & < \frac{\epsilon}{3} + \frac{\epsilon}{3} + \frac{\epsilon}{3} = \epsilon . \end{split} \end{equation*}

As \(\abs{a-b} < \epsilon\) for all \(\epsilon > 0\text{,}\) then \(a=b\) and the sequence converges.

Remark 2.4.6.

The statement of this theorem is sometimes used to define the completeness property of the real numbers. We say a set is Cauchy-complete (or sometimes just complete) if every Cauchy sequence converges to something in the set. Above, we proved that as \(\R\) has the least-upper-bound property, \(\R\) is Cauchy-complete. One can construct \(\R\) via “completing” \(\Q\) by “throwing in” just enough points to make all Cauchy sequences converge (we omit the details). The resulting field has the least-upper-bound property. The advantage of defining completeness via Cauchy sequences is that it generalizes to more abstract settings such as metric spaces, see Chapter 7.

The Cauchy criterion is stronger than \(\abs{x_{n+1}-x_n}\) (or \(\abs{x_{n+j}-x_n}\) for a fixed \(j\)) going to zero as \(n\) goes to infinity. When we get to the partial sums of the harmonic series (see Example 2.5.11 in the next section), we will have a sequence such that \(x_{n+1}-x_n = \nicefrac{1}{n}\text{,}\) yet \(\{ x_n \}_{n=1}^\infty\) is divergent. In fact, for that sequence, \(\lim_{n\to\infty} \abs{x_{n+j}-x_n} = 0\) for every \(j \in \N\) (compare Exercise 2.5.12). The key point in the definition of Cauchy is that \(n\) and \(k\) vary independently and can be arbitrarily far apart.

Subsection 2.4.1 Exercises

Exercise 2.4.1.

Prove that \(\{ \frac{n^2-1}{n^2} \}_{n=1}^\infty\) is Cauchy using directly the definition of Cauchy sequences.

Exercise 2.4.2.

Let \(\{ x_n \}_{n=1}^\infty\) be a sequence such that there exists a positive \(C < 1\) and for all \(n\text{,}\)

\begin{equation*} \abs{x_{n+1} - x_n} \leq C \abs{x_{n}-x_{n-1}} . \end{equation*}

Prove that \(\{ x_n \}_{n=1}^\infty\) is Cauchy. Hint: You can freely use the formula (for \(C \not= 1\))

\begin{equation*} 1+ C+ C^2 + \cdots + C^n = \frac{1-C^{n+1}}{1-C}. \end{equation*}

Exercise 2.4.3.

(Challenging) Suppose \(F\) is an ordered field that contains the rational numbers \(\Q\text{,}\) such that \(\Q\) is dense, that is: Whenever \(x,y \in F\) are such that \(x < y\text{,}\) then there exists a \(q \in \Q\) such that \(x < q < y\text{.}\) Say a sequence \(\{ x_n \}_{n=1}^\infty\) of rational numbers is Cauchy if given every \(\epsilon \in \Q\) with \(\epsilon > 0\text{,}\) there exists an \(M\) such that for all \(n,k \geq M\text{,}\) we have \(\abs{x_n-x_k} < \epsilon\text{.}\) Suppose every Cauchy sequence of rational numbers has a limit in \(F\text{.}\) Prove that \(F\) has the least-upper-bound property.

Exercise 2.4.4.

Let \(\{ x_n \}_{n=1}^\infty\) and \(\{ y_n \}_{n=1}^\infty\) be sequences such that \(\lim_{n\to\infty} y_n =0\text{.}\) Suppose that for all \(k \in \N\) and for all \(m \geq k\text{,}\) we have

\begin{equation*} \abs{x_m-x_k} \leq y_k . \end{equation*}

Show that \(\{ x_n \}_{n=1}^\infty\) is Cauchy.

Exercise 2.4.5.

Suppose a Cauchy sequence \(\{ x_n \}_{n=1}^\infty\) is such that for every \(M \in \N\text{,}\) there exists a \(k \geq M\) and an \(n \geq M\) such that \(x_k < 0\) and \(x_n > 0\text{.}\) Using simply the definition of a Cauchy sequence and of a convergent sequence, show that the sequence converges to \(0\text{.}\)

Exercise 2.4.6.

Suppose \(\abs{x_n-x_k} \leq \nicefrac{n}{k^2}\) for all \(n\) and \(k\text{.}\) Show that \(\{ x_n \}_{n=1}^\infty\) is Cauchy.

Exercise 2.4.7.

Suppose \(\{ x_n \}_{n=1}^\infty\) is a Cauchy sequence such that for infinitely many \(n\text{,}\) \(x_n = c\text{.}\) Using only the definition of Cauchy sequence prove that \(\lim\limits_{n\to\infty} x_n = c\text{.}\)

Exercise 2.4.8.

True or false, prove or find a counterexample: If \(\{ x_n \}_{n=1}^\infty\) is a Cauchy sequence, then there exists an \(M\) such that for all \(n \geq M\text{,}\) we have \(\abs{x_{n+1}-x_n} \leq \abs{x_{n}-x_{n-1}}\text{.}\)

Named after the French mathematician Augustin-Louis Cauchy (1789–1857).