Cauchy sequences – Serlo

Motivation

In the last chapter, we learned about convergence of sequences $a_{n}\to a$. They were defined via the Epsilon-criterion, which says that $|a_{n}-a|<\epsilon$ must hold for all but finitely many $a_{n}$. I.e. it holds for all $n\geq N$ with some $N\in \mathbb {N}$. However, in order to apply this criterion, we need a candidate for the limit $a$. What if we don't have such a candidate? Or more precisely,

How can we show that a sequence converges, if there is no candidate for the limit?

A sequence converges, if the distance of $a_{n}$ to $a$ eventually tends to 0. In that case, also the difference between elements $|a_{n}-a_{m}|$ tends to 0. Conversely, if we know that $|a_{n}-a_{m}|$ goes to 0 if both $n$ and $m$ get large, then the amount of points where a possible limit or accumulation point $a$ might be shrinks together to a point. So the sequence should converge, then

A sequence converges, whenever the difference of two elements eventually gets arbitrarily small.

The interesting question is now, what condition we have to put on $n$ and $m$. If we just consider neighbouring sequence elements via setting $m=n+1$, we might run into trouble: consider the sequence

$(x_{n})_{n\in \mathbb {N} }=\left(1,\,2,\,2{\tfrac {1}{2}},\,3,\,3{\tfrac {1}{3}},\,3{\tfrac {2}{3}},\,4,\,4{\tfrac {1}{4}},\,4{\tfrac {2}{4}},\,\ldots \right)$

This is a harmonic series. The difference of neighbouring elements is $|a_{n}-a_{n+1}|={\tfrac {1}{n}}\to 0$. But the sequence itself diverges to $\infty$. We need a stronger criterion, i.e. we need to consider more pairs $(n,m)$ than just neighbours.

Derivation of Cauchy sequences

We try to get a condition on $|a_{n}-a_{m}|$, which suffices for showing that a sequence converges. So let's take a sequence $(a_{n})_{n\in \mathbb {N} }$ converging to $a$ and play a bit with it: The epsilon-definition of convergence reads

$\forall \epsilon >0\,\exists N\in \mathbb {N} \,\forall n\geq N:|a-a_{n}|<\epsilon$

We fix $\epsilon >0$. Then, there is an index $N_{\epsilon }\in \mathbb {N}$ depending on $\epsilon$ with $|a-a_{n}|<\epsilon$ for all $n\geq N_{\epsilon }$ . What can we say about the difference $|a_{n}-a_{m}|$ for $n,m\geq N_{\epsilon }$? There is

${\begin{aligned}|a-a_{n}|&<\epsilon \\|a-a_{m}|&<\epsilon \end{aligned}}$

So the triangle inequality for $|a_{n}-a_{m}|$ implies:

${\begin{aligned}|a_{n}-a_{m}|&=|(a_{n}-a)+(a-a_{m})|\\[0.5em]&{\color {OliveGreen}\left\downarrow \ {\text{triangle inequality: }}|x+y|\leq |x|+|y|\right.}\\[0.5em]&\leq \underbrace {|a_{n}-a|} _{<\ \epsilon }+\underbrace {|a-a_{m}|} _{<\ \epsilon }\\&<2\epsilon \end{aligned}}$

Sequence elements coming after $a_{N_{\epsilon }}$ are all separated by less than $2\epsilon$ . Visually, all sequence elements are all situated inside the interval $(a-\epsilon ,a+\epsilon )$ which has width $2\epsilon$:

An Epsilon-neighbourhood of a

The distance between two points in this interval is less than $2\epsilon$ . So for a convergent sequence $(a_{n})_{n\in \mathbb {N} }$ we have:

$\forall \epsilon >0\,\exists N\in \mathbb {N} \,\forall n,m\geq N:|a_{n}-a_{m}|<2\epsilon$

The $2$, in here is a bit awkward to most mathematicians. They remove it by defining ${\tilde {\epsilon }}=2\epsilon$. The function $x\mapsto 2x$ is mapping $\mathbb {R} ^{+}$ bijectively onto $\mathbb {R} ^{+}$ . So instead saying "for all $\epsilon >0$", we could also use the term "for all ${\tilde {\epsilon }}>0$":

$\forall {\tilde {\epsilon }}>0\,\exists N\in \mathbb {N} \,\forall n,m\geq N:|a_{n}-a_{m}|<{\tilde {\epsilon }}$

Sequences, which fulfil the above property are called Cauchy sequences . This definition does not require a limit $a$ . A sequence which converges, fulfils the above property, so any convergent sequence is a Cauchy sequence. But seeing that any Cauchy sequence converges is not so easy. Generally, this is even wrong: Not every Cauchy sequence converges! However, it is true that every Cauchy sequence in $\mathbb {R}$ converges. In the rest this article , we successively construct a proof for this.

Hint

In the following section, we will again use $\epsilon$ instead of ${\tilde {\epsilon }}$.

Definition of a Cauchy sequence

An introduction to Cauchy sequences (video in German). (YouTube video by the channel Quatematik)

The definition for a Cauchy sequence reads:

Definition (Cauchy sequence)

A sequence $(a_{n})_{n\in \mathbb {N} }$ is called Cauchy sequence, if for any $\epsilon >0$ there is a natural number $N\in \mathbb {N}$ , such that $|a_{n}-a_{m}|<\epsilon$ for all $n,m\geq N$ .

Intuitively, a sequence is Cauchy, if the difference between any two elements gets arbitrarily small as the element indices go to $\infty$. Beware: it is a common mistake to think that only neighbouring elements must get close to each other. However, Cauchy sequences require all differences between elements to go to 0:

• 
  A Cauchy sequence: differences between two elements tend to 0.
• 
  Not a Cauchy sequence: differences do not tend to 0.

Example (A Cauchy sequence)

The sequence $(a_{n})_{n\in \mathbb {N} }$ with $a_{n}={\tfrac {1}{n}}$ converges, so it should be a Cauchy sequence. We may also directly check the definition: for any $\epsilon >0$ , we need to find an $N\in \mathbb {N}$ , such that for all $n,m\geq N$ there is

$|a_{n}-a_{m}|=\left|{\frac {1}{n}}-{\frac {1}{m}}\right|=\left|{\frac {m-n}{nm}}\right|={\frac {|m-n|}{nm}}<\epsilon$

We assume $n>m$ . The case $n<m$ works analogously by interchanging $n$ and $m$. Certainly,

$|a_{n}-a_{m}|={\frac {|m-n|}{nm}}<{\frac {n}{nm}}={\frac {1}{m}}$

Now, we take $N$ such that $N>{\tfrac {1}{\epsilon }}$ (the Archimedean axiom allows us to do so). Then, ${\tfrac {1}{N}}<\epsilon$ and hence ${\tfrac {1}{m}}<\epsilon$ for all $m\geq N$. So for all $n,m\in \mathbb {N}$ with $n>m\geq N$ there is:

$|a_{m}-a_{n}|={\frac {|m-n|}{mn}}<{\frac {1}{m}}\leq {\frac {1}{N}}<\epsilon$

and we get that $(a_{n})_{n\in \mathbb {N} }$ is a Cauchy sequence.

Example (Not a Cauchy sequence)

The sequence $(a_{n})_{n\in \mathbb {N} }$ with $a_{n}=n$ is not a Cauchy sequence. And it does not converge. We can check the Cauchy sequence definition directly: For any $\epsilon >0$ and $N\in \mathbb {N}$ we can choose $n,m\geq N$ far enough away, such that $|a_{n}-a_{m}|\geq \epsilon$ holds. This is particularly easy for $\epsilon ={\tfrac {1}{2}}$: any difference between to distinct elements is then $\geq 1>\epsilon$. So for a given $N\in \mathbb {N}$, we just set $n=N+1$ and $m=N+2$. Then

$|a_{m}-a_{n}|=|m-n|=|N+2-(N+1)|=1\geq {\tfrac {1}{2}}=\epsilon$

And $(a_{n})_{n\in \mathbb {N} }$ is by definition not a Cauchy sequence.

Every convergent sequence is a Cauchy sequence

We essentially already proved this within the "derivation of Cauchy sequences". But it's always a good idea, to write down one's findings in a structured way. So let's do this:

Theorem

Every convergent sequence is a Cauchy sequence.

How to get to the proof?

See "derivation of Cauchy sequences". The idea is to start with the $\epsilon$-definition of convergence and to directly prove that the Cauchy condition with ${\tilde {\epsilon }}$ holds true. This will be the case for ${\tilde {\epsilon }}=2\epsilon \Leftrightarrow \epsilon ={\tfrac {\tilde {\epsilon }}{2}}$.

Proof

Let $(a_{n})_{n\in \mathbb {N} }$ be any convergent sequence and ${\tilde {\epsilon }}>0$ be given. Then, there is an $N\in \mathbb {N}$ with

${\begin{aligned}|a-a_{n}|&<{\tfrac {\tilde {\epsilon }}{2}}\\|a-a_{m}|&<{\tfrac {\tilde {\epsilon }}{2}}\end{aligned}}$

for all $n,m\geq N$. Let now $n,m\geq N$ be arbitrary. Then,

${\begin{aligned}|a_{n}-a_{m}|&=|(a_{n}-a)+(a-a_{m})|\\[0.5em]&{\color {OliveGreen}\left\downarrow \ {\text{triangle inequality: }}|x+y|\leq |x|+|y|\right.}\\[0.5em]&\leq \underbrace {|a_{n}-a|} _{<\ {\tfrac {\epsilon }{2}}}+\underbrace {|a-a_{m}|} _{<\ {\tfrac {\epsilon }{2}}}<\epsilon \end{aligned}}$

Cauchy sequences are bounded

Convergent series are bounded. And we can prove the same for Cauchy sequences:

Theorem (Cauchy sequences are bounded)

Any Cauchy sequence is bounded.

This should not come as a surprise: if the distance $|a_{n}-a_{m}|$ is bounded, then, for a fixed $a_{m}$, there is now way for $a_{n}$ to escape to $\pm \infty$. Intuitively, $a_{m}$ "catches" $a_{n}$. And if a Cauchy sequence converges (we will find out that this is always the case in $\mathbb {R}$), then it must also be bounded:

Proof (Cauchy sequences are bounded)

Let $(a_{n})_{n\in \mathbb {N} }$ be a Cauchy sequence. We know that for any $\epsilon >0$ there is an $N\in \mathbb {N}$ with $|a_{n}-a_{m}|<\epsilon$ for all $n,m\geq N$ . Now, we just fix $\epsilon =1$ (actually, any positive real number is OK, here) and get some $N\in \mathbb {N}$ with $|a_{n}-a_{m}|<1$ for all $n,m\geq N$. Now, we fix $m=N$ and get

$|a_{n}-a_{N}|<1$

for all $n\geq N$. So all $a_{n}$ with $n\geq N$ are "caught" inside the interval $(a_{N}-1,a_{N}+1)$. That means, after passing index $N$, all sequence elements are bounded from above by $a_{N}+1$ and from below by $a_{N}-1$:

$(a_{n})_{n\in \mathbb {N} }=(a_{1},\,a_{2},\,\ldots ,\,a_{N-1},\,{\color {OliveGreen}\underbrace {a_{N},\,a_{N+1},\,a_{N+2},\,a_{N+3},\,\ldots } _{{\text{These are all }}\leq a_{N}+1{\text{ and }}\geq a_{N}-1}})$

Only the sequence elements before $a_{N}$ remain. But those are finitely many, namely $a_{1},\,a_{2},\,\ldots ,\,a_{N-1}$. A finite set of numbers is always bounded. So these "early sequence elements" are bounded from above by $S=\max\{a_{1},\,a_{2},\,\ldots ,\,a_{N-1}\}$ and from below by $s=\min\{a_{1},\,a_{2},\,\ldots ,\,a_{N-1}\}$ . For the entire sequence, there is

$(a_{n})_{n\in \mathbb {N} }=({\color {Blue}\underbrace {a_{1},\,a_{2},\,\ldots ,\,a_{N-1}} _{{\text{These elements are }}\leq S{\text{ and }}\geq s}},{\color {OliveGreen}\underbrace {a_{N},\,a_{N+1},\,a_{N+2},\,a_{N+3},\,\ldots } _{{\text{These elements are }}\leq a_{N}+1{\text{ and }}\geq a_{N}-1}})$

So the sequence $(a_{n})_{n\in \mathbb {N} }$ is bounded from above by $\max\{S,a_{N}+1\}$ and from below by $\min\{s,a_{N}-1\}$ .

Cauchy sequences with convergent subsequences also converge

We would like to show that in $\mathbb {R}$, a Cauchy sequence converges. This is a somewhat longer task. So we first take a smaller step and prove the following smaller theorem:

Theorem (Cauchy sequences with convergent subsequences also converge)

Any Cauchy sequence $(a_{n})_{n\in \mathbb {N} }$, with a subsequence $\left(a_{n_{k}}\right)_{k\in \mathbb {N} }$ converging to $a$ also converges to $a$.

How to get to the proof? (Cauchy sequences with convergent subsequences also converge)

Let $(a_{n})_{n\in \mathbb {N} }$ be a Cauchy sequence and $\left(a_{n_{k}}\right)_{k\in \mathbb {N} }$ a subsequence converging to $a$. For $(a_{n})_{n\in \mathbb {N} }$ , the difference $|a_{n}-a_{m}|$ gets very small and for the convergent subsequence, the elements tend to $a$. The idea is not to fix an element $a_{m}$ from the subsequence, which is close to $a$ and catch all $a_{n}$ after it by the Cauchy condition.

How close do we need to get? Suppose, $\epsilon >0$ is given. We need to find some $N\in \mathbb {N}$ such that $|a_{n}-a|<\epsilon$ for all $n\geq N$ . So the target inequality is

$|a_{n}-a|<\epsilon$

If $a_{n}$ is an element of the subsequence $\left(a_{n_{k}}\right)_{k\in \mathbb {N} }$ , this is not a problem. We could even get $\left|a_{n_{k}}-a\right|<{\tfrac {\epsilon }{2}}$ or smaller. And if $a_{n}$ is not part of the convergent subsequence? Then, we need to use the Cauchy-property. If we choose $n$ large enough, there will be elements $a_{n_{k}}$ of the subsequence with $n_{k}<n$. So we can bound $|a_{n}-a|$ using the triangle inequality:

${\begin{aligned}|a_{n}-a|&=\left|a_{n}-a_{n_{k}}+a_{n_{k}}-a\right|\\[0.5em]&{\color {OliveGreen}\left\downarrow \ {\text{triangle inequality}}\right.}\\[0.5em]&\leq \left|a_{n}-a_{n_{k}}\right|+\left|a_{n_{k}}-a\right|\end{aligned}}$

Both absolutes can be made arbitrarily small. Their sum must be smaller than $\epsilon$. This is fulfilled if we choose both absolutes to be smaller than ${\tfrac {\epsilon }{2}}$ . sIn order to get $\left|a_{n_{k}}-a\right|$ that small, we choose some $N_{1}$ with $\left|a_{n_{k}}-a\right|<{\tfrac {\epsilon }{2}}$ for all $k\geq N_{1}$. Such an $N_{1}$ exists, as $\left(a_{n_{k}}\right)_{k\in \mathbb {N} }$ converges to $a$ .

Now the second absolute value: By the Cauchy sequence property, there must be some $N_{2}$ with $|a_{n}-a_{m}|<{\tfrac {\epsilon }{2}}$ for all $n,m\geq N_{2}$. In place of $a_{m}$ , we choose $a_{n_{k}}$. So we need $n_{k}\geq N_{2}$ . We know that $n_{k}\geq k$, since $(n_{k})_{k\in \mathbb {N} }$ is an ascending number of positive integers. Therefore, we add the requirement $k\geq N_{2}$ , which implies $n_{k}\geq k\geq N_{2}$. If we now set $k\geq \max\{N_{2},N_{1}\}$. Note: any $k\geq \max\{N_{2},N_{1}\}$ will do that job, no matter how big.

So far, the variable $n$ only appeared within $|a_{n}-a_{m}|$ . Here, we required $n,m\geq N_{2}$ . So for $n$ , there is only one condition: $n\geq N_{2}$ . We satisfy it by choosing $N=N_{2}$. Now, we are ready to write down the proof.

Proof (Cauchy sequences with convergent subsequences also converge)

Let $(a_{n})_{n\in \mathbb {N} }$ be a Cauchy sequence and $\left(a_{n_{k}}\right)_{k\in \mathbb {N} }$ a subsequence converging to $a$. Let $\epsilon >0$ be arbitrary. By the Cauchy property, there is an $N\in \mathbb {N}$ with $|a_{n}-a_{m}|<{\tfrac {\epsilon }{2}}$ for all $n,m\geq N$ . In addition, there is an ${\tilde {N}}\in \mathbb {N}$ with $\left|a_{n_{k}}-a\right|<{\tfrac {\epsilon }{2}}$ for all $k\geq {\tilde {N}}$. Let ${\tilde {k}}$ be any natural number with ${\tilde {k}}\geq \max\{N,{\tilde {N}}\}$ and $n\geq N$ be arbitrary, as well. Then,

${\begin{aligned}|a_{n}-a|&=\left|a_{n}-a_{n_{\tilde {k}}}+a_{n_{\tilde {k}}}-a\right|\\[0.5em]&{\color {OliveGreen}\left\downarrow \ {\text{triangle inequality}}\right.}\\[0.5em]&\leq \left|a_{n}-a_{n_{\tilde {k}}}\right|+\left|a_{n_{\tilde {k}}}-a\right|\\[0.5em]&{\color {OliveGreen}\left\downarrow \ \left|a_{n_{\tilde {k}}}-a\right|<{\tfrac {\epsilon }{2}}\right.}\\[0.5em]&<\left|a_{n}-a_{n_{\tilde {k}}}\right|+{\tfrac {\epsilon }{2}}\\[0.5em]&{\color {OliveGreen}\left\downarrow \ n_{k}\geq {\tilde {k}}\geq N\Rightarrow \left|a_{n}-a_{n_{\tilde {k}}}\right|<{\tfrac {\epsilon }{2}}\right.}\\[0.5em]&<{\tfrac {\epsilon }{2}}+{\tfrac {\epsilon }{2}}=\epsilon \end{aligned}}$

Every Cauchy sequence converges

Converges of Cauchy sequences (video by the channel MJ Education, in German).

Now, that we have the smaller theorem above, we can use it to show the final theorem:

Theorem (Every Cauchy sequence converges)

Let $(a_{n})_{n\in \mathbb {N} }$ be a real Cauchy sequence. Then, $(a_{n})_{n\in \mathbb {N} }$ converges to some $a\in \mathbb {R}$.

This theorem is of particularly high value, since it allows to show convergence of a sequence without having a candidate for a limit.

Before proving it, we will stress out that there are sets where not every Cauchy sequence converges. For instance, we might want to replace the condition $a\in \mathbb {R}$ by $a\in \mathbb {Q}$ (rational numbers). However, there are some possible limits, which are in $\mathbb {R}$, but not in $\mathbb {Q}$. For instance, take $a={\sqrt {2}}=1{,}414213562\ldots$ , which is the limit of the rational sequence

${\begin{aligned}x_{1}&=1\\x_{2}&=1{,}4\\x_{3}&=1{,}41\\&\vdots \end{aligned}}$

in $\mathbb {R}$, this sequence converges to ${\sqrt {2}}$. So it is a Cauchy sequence $\mathbb {R}$. Since the Cauchy condition is sustained under the replacement $\mathbb {R} \to \mathbb {Q}$, this is also a Cauchy sequence in $\mathbb {Q}$. However, in $\mathbb {R}$, the limit $a={\sqrt {2}}$ is unique, so there cannot be a further limit $a\in \mathbb {Q}$. Hence, we have found a Cauchy sequence, which does not converge. We conclude, there are sets like $\mathbb {Q}$, where Cauchy sequences may not converge. The crucial point her is that $\mathbb {R}$ is complete, while $\mathbb {Q}$ is not. We have already encountered completeness within the Bolzano-Weierstrass theorem, where it was necessary for the theorem to hold true. Similarly, completeness is also necessary for a Cauchy sequence to converge.

Proof (Every Cauchy sequence converges)

Let $(a_{n})_{n\in \mathbb {N} }$ be a Cauchy sequence. Two subsections above, we proved that this implies boundedness. By the Bolzano-Weierstrass theorem, every bounded sequence has a convergent subsequence. So the Cauchy sequence has a convergent subsequence. One subsection above, we proved that any Cauchy sequence with a convergent subsequence also converges to some $a$. So $(a_{n})_{n\in \mathbb {N} }$ must converge to some $a$, which finishes the proof.