# Cauchy's Convergence Criterion/Real Numbers/Sufficient Condition/Proof 3

## Theorem

Let $\sequence {x_n}$ be a sequence in $\R$.

Let $\sequence {x_n}$ be a Cauchy sequence.

Then $\sequence {x_n}$ is convergent.

## Proof

Let $\sequence {a_n}$ be a Cauchy sequence in $\R$.

Let $\epsilon \in \R_{>0}$ be given.

Since $\sequence {a_n}$ is Cauchy, a natural number $N$ exists such that:

$\size {a_n - a_m} < \epsilon$ for every $m, n \ge N$

We aim to show that $\sequence {a_n}$ converges.

That is, that numbers $a$ in $\R$ and $N'$ in $\N$ exist such that:

$\size {a_n - a} < \epsilon$ for every $n > N'$

Let $\sequence {\epsilon_i}_{i \mathop \in \N}$ be a sequence of strictly positive real numbers that satisfies:

$\epsilon_0 = \epsilon$
$\epsilon_{i + 1} < \epsilon_i$ for every $i \in \N$
$\ds \lim_{i \mathop \to \infty} \epsilon_i = 0$

### $\sequence {a_n}$ is between two other sequences

Since $\sequence {a_n}$ is Cauchy, for each $\epsilon_i$ a natural number $N_i$ exists such that:

$\size {a_n - a_m} < \epsilon_i$ for every $m, n \ge N_i$

Let us study the sequence $\sequence {N_i}_{i \mathop \in \N}$.

First, we consider $N_0$.

We can choose $N_0 = N$ because $(1)$ $\size {a_n - a_m} < \epsilon$ for every $m, n \ge N$ and $(2)$ $\epsilon = \epsilon_0$.

Next, we consider the relation between $N_{i + 1}$ and $N_i$.

We have, for $i \in \N$:

$\size {a_n - a_m} < \epsilon_i$ for every $m, n \ge N_i$

and:

$\size {a_n - a_m} < \epsilon_{i + 1}$ for every $m, n \ge N_{i + 1}$

There are two cases for $\size {a_n - a_m}$ when $m, n \ge N_i$.

Either:

$\size {a_n - a_m} < \epsilon_{i + 1}$ for every $m, n \ge N_i$

or:

$\size {a_{n'} - a_{m'} } \ge \epsilon_{i + 1}$ for some $m', n' \ge N_i$

In the first case, we can choose $N_{i + 1} = N_i$ since $\size {a_n - a_m} < \epsilon_{i + 1}$ for every $m, n \ge N_i$.

In the second case, suppose that $m', n' \ge N_{i + 1}$.

This cannot be true since $\size {a_n - a_m} < \epsilon_{i + 1}$ for every $m, n \ge N_{i + 1}$.

Therefore, at least one of $m', n'$, call it $k'$, must be less than $N_{i + 1}$.

This means that:

 $\ds N_i$ $\le$ $\ds k' < N_{i + 1}$ $\ds \leadsto \ \$ $\ds N_i$ $<$ $\ds N_{i + 1}$

Thus, we have established that there exists a sequence $\sequence {N_i}_{i \mathop \in \N}$ that satisfies:

$N_0 = N$
$N_{i + 1} \ge N_i$ for every $i \in \N$

Since $\sequence {a_n}$ is Cauchy, we have for every $i \in \N$:

 $\ds \size {a_n - a_m}$ $<$ $\ds \epsilon_i$ for every $m, n \ge N_i$ $\ds \leadsto \ \$ $\ds \size {a_n - a_{N_i} }$ $<$ $\ds \epsilon_i$ for every $n \ge N_i$ $\ds \leadsto \ \$ $\ds a_{N_i} - \epsilon_i$ $<$ $\ds a_n < a_{N_i} + \epsilon_i$ for every $n \ge N_i$ by Negative of Absolute Value: Corollary 1

$\Box$

Define a real sequence $\sequence {u_i}_{i \mathop \in \N}$ by:

$u_0 = a_{N_0} + \epsilon_0$
$u_{i + 1} = \min \set {u_i, a_{N_{i + 1} } + \epsilon_{i + 1} }$ for every $i \in \N$

We observe that $u_{i + 1}$ is the minimum of two numbers, one of which is $u_i$.

Therefore $\sequence {u_i}$ is decreasing.

### $u_i$ is an upper bound for $\sequence {a_n}_{n \mathop \ge N_i}$

We prove this by using the Principle of Mathematical Induction.

$a_{N_0} + \epsilon_0$ is an upper bound for $\sequence {a_n}_{n \mathop \ge N_0}$ because $a_n < a_{N_0} + \epsilon_0$ whenever $n \ge N_0$.

Therefore, $u_0$ is an upper bound for $\sequence {a_n}_{n \mathop \ge N_0}$ since $u_0 = a_{N_0} + \epsilon_0$.

This concludes the first induction step.

We need to prove that $u_{i + 1}$ is an upper bound for $\sequence {a_n}_{n \mathop \ge N_{i + 1} }$ if $u_i$ is an upper bound for $\sequence {a_n}_{n \mathop \ge N_i}$.

$u_{i + 1}$ equals either $u_i$ or $a_{N_{i + 1} } + \epsilon_{i + 1}$.

First, assume that $u_{i + 1} = u_i$.

$u_{i + 1}$ is an upper bound for $\sequence {a_n}_{n \mathop \ge N_i}$ since $u_i$ is an upper bound for $\sequence {a_n}_{n \mathop \ge N_i}$ by presupposition.

We have that $\sequence {a_n}_{n \mathop \ge N_{i + 1} }$ is a subset of $\sequence {a_n}_{n \mathop \ge N_i}$ because $N_{i + 1} \ge N_i$.

Therefore, $u_{i + 1}$ is an upper bound for $\sequence {a_n}_{n \mathop \ge N_{i + 1} }$ because $u_{i + 1}$ is an upper bound for $\sequence {a_n}_{n \mathop \ge N_i}$.

Now, assume that $u_{i + 1} = a_{N_{i + 1} } + \epsilon_{i + 1}$.

$u_{i + 1}$ is an upper bound for $\sequence {a_n}_{n \mathop \ge N_{i + 1} }$ because $a_n < a_{N_{i + 1} } + \epsilon_{i + 1}$ whenever $n \ge N_{i + 1}$.

This concludes the proof that $u_i$ is an upper bound for $\sequence {a_n}_{n \mathop \ge N_i}$ for every $i \in \N$.

$\Box$

### $\sequence {u_i}$ converges

By Real Cauchy Sequence is Bounded, $\sequence {a_n}$ is bounded.

Therefore, $\sequence {a_n}$ has a lower bound $b$.

For every $i \in \N$, $\sequence {a_n}_{n \mathop \ge N_i}$ is a subsequence of $\sequence {a_n}$.

Therefore, $b$ is also a lower bound for $\sequence {a_n}_{n \mathop \ge N_i}$.

$u_i$ is an upper bound for $\sequence {a_n}_{n \mathop \ge N_i}$.

Therefore, $b$ is less than or equal to $u_i$ for every $i$.

So, $\sequence {u_i}$ is bounded below.

Since $\sequence {u_i}$ is decreasing, its first element is an upper bound for $\sequence {u_i}$.

Since $\sequence {u_i}$ is bounded below and above, it is bounded.

We have that$\sequence {u_i}$ is bounded and decreasing.

Therefore $\sequence {u_i}$ converges by the Monotone Convergence Theorem.

$\Box$

Now, define a real sequence $\sequence {l_i}_{i \mathop \in \N}$ by:

$l_0 = a_{N_0} - \epsilon_0$
$l_{i + 1} = \max \set {l_i, a_{N_{i + 1} } - \epsilon_{i + 1} }$ for every $i \in \N$

### $l_i$ is a lower bound for $\sequence {a_n}_{n \mathop \ge N_i}$, and $\sequence {l_i}$ converges

An analysis of $\sequence {l_i}$ is similar to the one above of $\sequence {u_i}$.

Therefore, it is not given here.

It produces the following results:

$\sequence {l_i}$ is increasing
$l_i$ is a lower bound for $\sequence {a_n}_{n \mathop \ge N_i}$ for every $i \in \N$
$\sequence {l_i}$ converges

$\Box$

### The limits of $\sequence {u_i}$ and $\sequence {l_i}$ as $i \to \infty$ are equal

Since $u_i$ and $l_i$ are, respectively, upper and lower bounds for $\sequence {a_n}_{n \mathop \ge N_i}$ for every $i \in \N$, we have for every $i \in \N$:

 $\ds 0$ $\le$ $\ds u_{i + 1} - l_{i + 1}$ $\ds$ $=$ $\ds \min \set {u_i, a_{N_{i + 1} } + \epsilon_{i + 1} } - \max \set {l_i, a_{N_{i + 1} } - \epsilon_{i + 1} }$ Definitions of $u_{i + 1}$ and $l_{i + 1}$ $\ds$ $\le$ $\ds a_{N_{i + 1} } + \epsilon_{i + 1} - \max \set {l_i, a_{N_{i + 1} } - \epsilon_{i + 1} }$ because $\min \set {u_i, a_{N_{i + 1} } + \epsilon_{i + 1} } \le a_{N_{i + 1} } + \epsilon_{i + 1}$ $\ds$ $\le$ $\ds a_{N_{i + 1} } + \epsilon_{i + 1} - \paren {a_{N_{i + 1} } - \epsilon_{i + 1} }$ because $\max \size {l_i, a_{N_{i + 1} } - \epsilon_{i + 1} } \ge a_{N_{i + 1} } - \epsilon_{i + 1}$ $\ds$ $=$ $\ds 2 \epsilon_{i + 1}$

This shows that $u_i - l_i \to 0$ as $i \to \infty$ since $\ds \lim_{i \mathop \to \infty} \epsilon_i = 0$.

We have:

 $\ds \lim_{i \mathop \to \infty} u_i - \lim_{i \mathop \to \infty} l_i$ $=$ $\ds \lim_{i \mathop \to \infty} (u_i - l_i)$ Combined Sum Rule for Real Sequences as $\sequence {u_i}$ and $\sequence {l_i}$ converge $\ds \leadstoandfrom \ \$ $\ds \lim_{i \mathop \to \infty} u_i - \lim_{i \mathop \to \infty} l_i$ $=$ $\ds 0$ as $\ds \lim_{i \mathop \to \infty} (u_i - l_i) = 0$ $\ds \leadstoandfrom \ \$ $\ds \lim_{i \mathop \to \infty} u_i$ $=$ $\ds \lim_{i \mathop \to \infty} l_i$

$\Box$

### $\sequence {a_n}$ converges

Let $\ds a = \lim_{i \mathop \to \infty} u_i = \lim_{i \mathop \to \infty} l_i$.

We have for every $i \in \N$:

 $\ds l_i$ $\le$ $\ds a \le u_i$ as $\sequence {l_i}$ is increasing and $\sequence {u_i}$ is decreasing $\ds \leadstoandfrom \ \$ $\ds 0$ $\le$ $\ds a - l_i \le u_i - l_i$

Also, we have for every $n \ge N_i$ for every $i \in \N$:

 $\ds l_i$ $\le$ $\ds a_n \le u_i$ as $l_i$ is a lower bound for $\sequence {a_n}_{n \ge N_i}$ and $u_i$ is an upper bound for $\sequence {a_n}_{n \mathop \ge N_i}$ $\ds \leadstoandfrom \ \$ $\ds 0$ $\le$ $\ds a_n - l_i \le u_i - l_i$

A natural number $j$ exists such that, for every $i \ge j$:

 $\ds \size {u_i - l_i}$ $<$ $\ds \dfrac \epsilon 2$ as $\ds \lim_{k \mathop \to \infty} (u_k - l_k) = 0$

Putting all this together, we find for every $n \ge N_j$:

 $\ds \size {a_n - a}$ $=$ $\ds \size {a_n - l_j + l_j - a}$ $\ds$ $\le$ $\ds \size {a_n - l_j} + \size {l_j - a}$ Triangle Inequality for Real Numbers $\ds$ $\le$ $\ds \size {u_j - l_j} + \size {l_j - a}$ as $0 \le a_n - l_j \le u_j - l_j$ $\ds$ $\le$ $\ds \size {u_j - l_j} + \size {u_j - l_j}$ as $0 \le a - l_j \le u_j - l_j$ $\ds$ $=$ $\ds 2 \size {u_j - l_j}$ $\ds$ $<$ $\ds \epsilon$ as $\ds \size {u_j - l_j} < \frac \epsilon 2$

This finishes the proof that $\sequence {a_n}$ is convergent.

$\blacksquare$