# Cauchy sequences – Serlo

## Motivation

In the last chapter, we learned about convergence of sequences ${\displaystyle a_{n}\to a}$. They were defined via the Epsilon-criterion, which says that ${\displaystyle |a_{n}-a|<\epsilon }$ must hold for all but finitely many ${\displaystyle a_{n}}$. I.e. it holds for all ${\displaystyle n\geq N}$ with some ${\displaystyle N\in \mathbb {N} }$. However, in order to apply this criterion, we need a candidate for the limit ${\displaystyle 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 ${\displaystyle a_{n}}$ to ${\displaystyle a}$ eventually tends to 0. In that case, also the difference between elements ${\displaystyle |a_{n}-a_{m}|}$ tends to 0. Conversely, if we know that ${\displaystyle |a_{n}-a_{m}|}$ goes to 0 if both ${\displaystyle n}$ and ${\displaystyle m}$ get large, then the amount of points where a possible limit or accumulation point ${\displaystyle 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 ${\displaystyle n}$ and ${\displaystyle m}$. If we just consider neighbouring sequence elements via setting ${\displaystyle m=n+1}$, we might run into trouble: consider the sequence

${\displaystyle (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 ${\displaystyle |a_{n}-a_{n+1}|={\tfrac {1}{n}}\to 0}$. But the sequence itself diverges to ${\displaystyle \infty }$. We need a stronger criterion, i.e. we need to consider more pairs ${\displaystyle (n,m)}$ than just neighbours.

## Derivation of Cauchy sequences

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

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

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

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

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

{\displaystyle {\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 ${\displaystyle a_{N_{\epsilon }}}$ are all separated by less than ${\displaystyle 2\epsilon }$ . Visually, all sequence elements are all situated inside the interval ${\displaystyle (a-\epsilon ,a+\epsilon )}$ which has width ${\displaystyle 2\epsilon }$:

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

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

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

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle \mathbb {R} }$ converges. In the rest this article , we successively construct a proof for this.

Hint

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

## Definition of a Cauchy sequence

The definition for a Cauchy sequence reads:

Definition (Cauchy sequence)

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

Example (A Cauchy sequence)

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

${\displaystyle |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 ${\displaystyle n>m}$ . The case ${\displaystyle n works analogously by interchanging ${\displaystyle n}$ and ${\displaystyle m}$. Certainly,

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

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

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

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

Example (Not a Cauchy sequence)

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

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

And ${\displaystyle (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 ${\displaystyle \epsilon }$-definition of convergence and to directly prove that the Cauchy condition with ${\displaystyle {\tilde {\epsilon }}}$ holds true. This will be the case for ${\displaystyle {\tilde {\epsilon }}=2\epsilon \Leftrightarrow \epsilon ={\tfrac {\tilde {\epsilon }}{2}}}$.

Proof

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

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

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

{\displaystyle {\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 ${\displaystyle |a_{n}-a_{m}|}$ is bounded, then, for a fixed ${\displaystyle a_{m}}$, there is now way for ${\displaystyle a_{n}}$ to escape to ${\displaystyle \pm \infty }$. Intuitively, ${\displaystyle a_{m}}$ "catches" ${\displaystyle a_{n}}$. And if a Cauchy sequence converges (we will find out that this is always the case in ${\displaystyle \mathbb {R} }$), then it must also be bounded:

Proof (Cauchy sequences are bounded)

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

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

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

${\displaystyle (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 ${\displaystyle a_{N}}$ remain. But those are finitely many, namely ${\displaystyle 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 ${\displaystyle S=\max\{a_{1},\,a_{2},\,\ldots ,\,a_{N-1}\}}$ and from below by ${\displaystyle s=\min\{a_{1},\,a_{2},\,\ldots ,\,a_{N-1}\}}$ . For the entire sequence, there is

${\displaystyle (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 ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ is bounded from above by ${\displaystyle \max\{S,a_{N}+1\}}$ and from below by ${\displaystyle \min\{s,a_{N}-1\}}$ .

## Cauchy sequences with convergent subsequences also converge

We would like to show that in ${\displaystyle \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 ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$, with a subsequence ${\displaystyle \left(a_{n_{k}}\right)_{k\in \mathbb {N} }}$ converging to ${\displaystyle a}$ also converges to ${\displaystyle a}$.

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

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

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

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

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

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

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

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

Proof (Cauchy sequences with convergent subsequences also converge)

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

{\displaystyle {\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

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

Theorem (Every Cauchy sequence converges)

Let ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ be a real Cauchy sequence. Then, ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ converges to some ${\displaystyle 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 ${\displaystyle a\in \mathbb {R} }$ by ${\displaystyle a\in \mathbb {Q} }$ (rational numbers). However, there are some possible limits, which are in ${\displaystyle \mathbb {R} }$, but not in ${\displaystyle \mathbb {Q} }$. For instance, take ${\displaystyle a={\sqrt {2}}=1{,}414213562\ldots }$ , which is the limit of the rational sequence

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

in ${\displaystyle \mathbb {R} }$, this sequence converges to ${\displaystyle {\sqrt {2}}}$. So it is a Cauchy sequence ${\displaystyle \mathbb {R} }$. Since the Cauchy condition is sustained under the replacement ${\displaystyle \mathbb {R} \to \mathbb {Q} }$, this is also a Cauchy sequence in ${\displaystyle \mathbb {Q} }$. However, in ${\displaystyle \mathbb {R} }$, the limit ${\displaystyle a={\sqrt {2}}}$ is unique, so there cannot be a further limit ${\displaystyle a\in \mathbb {Q} }$. Hence, we have found a Cauchy sequence, which does not converge. We conclude, there are sets like ${\displaystyle \mathbb {Q} }$, where Cauchy sequences may not converge. The crucial point her is that ${\displaystyle \mathbb {R} }$ is complete, while ${\displaystyle \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 ${\displaystyle (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 ${\displaystyle a}$. So ${\displaystyle (a_{n})_{n\in \mathbb {N} }}$ must converge to some ${\displaystyle a}$, which finishes the proof.