# Math for Non-Geeks/Cauchy sequences
## 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,
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
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$:
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

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

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.