12 Cauchy Sequences

Highlights of this Chapter: We define the notion of a Cauchy sequence, and we prove that being Cauchy is equivalent to being convergent.

One reasonably ambitious sounding goal in the study of sequences is to find a nice criterion to determine exactly when a sequence converges or not. We made partial progress towards this in the previous two chapters, and our goal in this chapter is to provide an alternative complete characterization, by a single simple property. But what could such a property be? One (good!) thought is the following

When a sequence converges, terms eventually get close to some limit $L$ . Thus the terms of the sequence eventually get close to one another.

This condition is certainly necessary: if the terms of a sequence do not get close together, then they cannot get close to any limit! But is it sufficiently precise to actually work? For that we need to turn it into a mathematical definition: perhaps

For all $ϵ > 0$ there is an $N$ where if $n > N$ then $| a_{n} - a_{n + 1} | < ϵ$

Unfortunately this doesn’t quite seem to work: perhaps surprisingly, it is possible for consecutive terms of a sequence to all get within $ϵ$ of one another, but for the overall sequence to diverge.

Example 12.1 ( $| a_{n} - a_{n + 1} |$ small but $a_{n}$ diverges!) Consider the sequence $a_{n} = \sqrt{n}$ . Then for all $ϵ > 0$ there is an $N$ where $n > N$ implies $| \sqrt{n} - \sqrt{n + 1} | < ϵ$ , but nonetheless $a_{n}$ diverges (to infinity).

Proof. We can estimate the difference between consecutive terms with some algebra: $\begin{aligned} \sqrt{n + 1} - \sqrt{n} & = (\sqrt{n + 1} - \sqrt{n}) \frac{\sqrt{n + 1} + \sqrt{n}}{\sqrt{n + 1} + \sqrt{n}} \\ = \frac{(n + 1) - n}{\sqrt{n + 1} + \sqrt{n}} \\ = \frac{1}{\sqrt{n + 1} + \sqrt{n}} \\ < \frac{1}{\sqrt{n}} \end{aligned}$ Thus for any $ϵ > 0$ we can just take $N = \frac{1}{ϵ^{2}}$ and see that if $n > N$ we have $| a_{n + 1} - a_{n} | < \frac{1}{\sqrt{n}} < \frac{1}{\sqrt{N}} = \frac{1}{\sqrt{\frac{1}{ϵ^{2}}}} = ϵ$

Nowever, $a_{n}$ is not converging to any finite number, as for any $M > 0$ , if $n > M^{2}$ then $a_{n} = \sqrt{n} > M$ , so $a_{n} \to \infty$ by Definition 8.4

Example 12.2 ( $| a_{n} - a_{n + 1} |$ small but $a_{n}$ diverges, again!) Perhaps the most famous example with this property is the harmonic series $a_{n} = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ Here it is clear that $a_{n} - a_{n + 1} = \frac{1}{n + 1}$ and we know this can be made smaller than any $ϵ > 0$ . However, as we will prove in CITE, this sequence nonetheless diverges to infinity.

So, we need to ask for a stronger condition. What went wrong? Well, even though we forced $a_{n}$ to be close to $a_{n + 1}$ for all $n$ , the small differences between consecutive terms could still manage to add up to big differences between terms: even if $a_{n}$ was within $0.01$ of $a_{n + 1}$ for all $n$ , its totally possible that $a_{n + 100, 000}$ could differ from $a_{n}$ by $(0.01) (10, 000) = 100$ ! So, to strengthen our definition we might try to impose that all terms of the sequence eventually stay close together:

Definition 12.1 (Cauchy Sequence) A sequence $s_{n}$ is Cauchy if for all $ϵ > 0$ there is a threshold past which any two terms of the sequence differ from one another by at most $ϵ$ . As a logic sentence, $\forall ϵ > 0 \exists N \forall m, n > N | s_{n} - s_{m} | < ϵ$

Example 12.3 (Cauchy Sequences: An Example) The sequence $s_{n} = \frac{1}{n}$ is cauchy: we can see this because for any $n, m$ $| \frac{1}{n} - \frac{1}{m} | < | \frac{1}{n} - 0 | = \frac{1}{n}$ And we already know that for any $ϵ$ we can choose $N$ with $n > N$ implying $1 / n < ϵ$ .

Example 12.4 (Cauchy Sequences: A Nonexample) The sequence $s_{n} = 1, 0, 1, 0, 1, 0 \dots$ is not Cauchy, as the difference between any two consecutive terms is $1$ . Thus for $ϵ = 1 / 2$ there is no $N$ where past that $N$ , every $s_{n}$ is within $1 / 2$ of each other.

Exercise 12.1 Is the sequence $s_{n} = 1 - \frac{(- 1)^{n}}{n}$ cauchy nor not? Prove your claim.

Exercise 12.2 Let $s_{n}$ be a periodic sequence (meaning after some period $P$ we have $s_{n} = s_{P + n}$ for all $n$ ). Prove that if $s_{n}$ is Cauchy then it is constant. Hint: what’s the contrapositive?

12.1 $★$ Properties of Cauchy Sequences

A good way to get used to a new definition is to use it. This definition looks very similar to the limit definition, which means we can often formulate analogous theorems and proofs to things we’ve seen before:

Note the proofs in this section are not logically required as the next section will render them superfluous: once we know Cauchy and convergent are equivalent, these all follow as immediate corollaries of the limit laws! Nonetheless it is instructive to see their direct proofs:

Proposition 12.1 (Cauchy Implies Bounded) If $s_{n}$ is Cauchy then its bounded: there exists a $B$ such that $| s_{n} | < B$ for all $n \in N$ .

Very similar to proof for convergent seqs Proposition 9.2 in style, where we show after some $N$ all the terms are bounded by some particular number, and then take the max of this and the (finitely many!) previous terms to get a bound on the entire sequence. :::{.proof} Set $ϵ = 1$ . Since $a_{n}$ is Cauchy we know there is some $N$ beyond which $| a_{n} - a_{m} | < 1$ for all $n, m > N$ . In particular, this means every |a_n-a_{N+1}|<1$ so $a_{N + 1} - 1 < a_{n} < a_{N + 1} + 1$ Thus for the (infinitely many terms!) after $a_{N}$ , we can bound all of them above by $a_{N + 1} + 1$ and below by $a_{N + 1} - 1$ . To extend these to bounds for the whole sequence, we just take the max or min with the (finitely many!) previous terms: $L = min {a_{1}, a_{2}, \dots, a_{N}, a_{N + 1} - 1}$ $U = max {a_{1}, a_{2}, \dots, a_{N}, a_{N + 1} + 1}$

Now we have for all $n$ , $L \leq a_{n} \leq U$ so ${a_{n}}$ is bounded. :::

Proposition 12.2 (Sums of Cauchy Sequences) If $a_{n}$ and $b_{n}$ are Cauchy sequences, so is $a_{n} + b_{n}$ .

Proof. Let $ϵ > 0$ . Then choose $N_{a}$ and $N_{b}$ such that for all $n, m$ greater than $N_{a}, N_{b}$ respectively, we have $| a_{n} - a_{m} | < ϵ / 2$ and $| b_{n} - b_{m} | < ϵ / 2$ . Set $N = max {N_{a}, N_{b}}$ and let $n, m > N$ . Then each of the above two inequalities hold, and so by the triangle inequality $| (a_{n} + b_{n}) - (a_{m} - b_{m}) | = | (a_{n} - a_{m}) + (b_{n} - b_{m}) |$ $\leq | a_{n} - a_{m} | + | b_{n} - b_{m} | < \frac{ϵ}{2} + \frac{ϵ}{2} = ϵ$

Thus, $a_{n} + b_{n}$ is Cauchy as well.

Exercise 12.3 (Constant Multiples of Cauchy Sequences) Let $a_{n}$ be Cauchy, and $k \in R$ be constant. Then $k a_{n}$ is Cauchy.

Proposition 12.3 (Products of Cauchy Sequences) Let $a_{n}, b_{n}$ be Cauchy. Then $s_{n} = a_{n} b_{n}$ is a cauchy sequence.

First, some scratch work: we are going to want to work with the condition $| s_{n} - s_{m} | = | a_{n} b_{n} - a_{m} b_{m} |$ . But we only know things about the quantities $| a_{n} - a_{m} |$ and $| b_{n} - b_{m} |$ . So, we need to do some algebra, involving adding zero in a clever way and applying the triangle inequality:

$\begin{aligned} | a_{n} b_{n} - a_{m} b_{m} | & = | a_{n} b_{n} + (a_{n} b_{m} - a_{n} b_{m}) - a_{m} b_{m} | \\ = | (a_{n} b_{n} - a_{n} b_{m}) + (a_{n} b_{m} - a_{m} b_{m}) | \\ = | a_{n} (b_{n} - b_{m}) + b_{m} (a_{n} - a_{m}) | \\ \leq | a_{n} (b_{n} - b_{m}) | + | b_{m} (a_{n} - a_{m}) | \\ = | a_{n} | | b_{n} - b_{m} | + | b_{m} | | a_{n} - a_{m} | \end{aligned}$

Because we know Cauchy sequences are bounded, we can get upper estimates for both $| a_{n} |$ and $| b_{n} |$ . And then as we know that the sequences are Cauchy, we can make $| a_{n} - a_{m} |$ and $| b_{n} - b_{m} |$ as small as we need, so that this overall term is small. We carry this idea out precisely in the proof below.

Proof. Let $a_{n}$ and $b_{n}$ be Cauchy, and choose an $ϵ > 0$ . Then each are bounded, so we can choose some $M_{a}$ with $| a_{n} | < M_{a}$ and $M_{b}$ where $| b_{n} | < M_{b}$ for all $n$ . To make notation easier, set $M = max {M_{a}, M_{b}}$ so that we know both $a_{n}$ and $b_{n}$ are bounded by the same constant $M$ .

Using that each is Cauchy, we can also get an $N_{a}$ and $N_{b}$ where if $n, m$ are greater than these respectively, we know that $| a_{n} - a_{m} | < \frac{ϵ}{2 M} | b_{n} - b_{m} | < \frac{ϵ}{2 M}$ Then set $N = max {N_{a}, N_{b}}$ , and choose arbitrary $n, m > N$ . Since in this case both of the above hypotheses are satisfied, we know that $| a_{n} | | b_{n} - b_{m} | \leq M \frac{ϵ}{2 M} = \frac{ϵ}{2} | b_{m} | | a_{n} - a_{m} | \leq M \frac{ϵ}{2 M} = \frac{ϵ}{2}$ Together, this means their sum is less than $ϵ$ , and from our scratch work we see their sum is already an upper bound for the quantity we are actually interested in: $| a_{n} b_{n} - a_{m} b_{m} | \leq | a_{n} | | b_{n} - b_{m} | + | b_{m} | | a_{n} - a_{m} | \leq ϵ$

Exercise 12.4 (Reciprocals of Cauchy Sequences) Let $a_{n}$ be a Cauchy sequence with $a_{n} \neq 0$ for all $n$ , which does not converge to zero. Then the sequence of reciprocals $s_{n} = \frac{1}{a_{n}}$ is Cauchy.

Just like for convergence, once we know the results products and reciprocals, quotients follow as an immediate corollary:

Corollary 12.1 (Quotients of Cauchy Sequences) If $a_{n}$ and $b_{n}$ are Cauchy with $b_{n} \neq 0$ and $lim b_{n} \neq 0$ then the quotients $a_{n} / b_{n}$ form a Cauchy sequence.

Exercise 12.5 Show the hypothesis $b_{n} ↛ 0$ is necessary in Corollary 12.1 by giving an example of two Cauchy sequences $a_{n}, b_{n}$ where $b_{n} \neq 0$ for all $n$ , yet $\frac{a_{n}}{b_{n}}$ is not a Cauchy sequence.

12.2 Cauchy $⟺$ Convergent

Now we move on to the main act, where we prove convergence is equivalent to Cauchy by showing an implication in both directions.

Exercise 12.6 (Convergent Implies Cauchy) If $s_{n}$ is a convergent sequence, then $s_{n}$ is Cauchy. Hint: The triangle inequality and $| a_{n} - a_{m} |$ for a sequence converging to $L$ can tell you….what?

More difficult, and more interesting, is the converse:

Proposition 12.4 (Cauchy Implies Convergent) If $s_{n}$ is a Cauchy sequence, then $s_{n}$ is convergent.

Proof. Let $s_{n}$ be a Cauchy sequence. Then it is bounded, by Proposition 12.1, so by the Bolzano Weierstrass theorem (?thm-thm-bolzano-weierstrass) we can extract a subsequence $s_{n_{k}}$ which converges to some real number $L$ .

Now we have something to work with, and all we need to show is that the rest of the sequence also converges to $L$ . So, let’s fix an $ϵ > 0$ . Since $s_{n_{k}} \to L$ there exists an $N_{1}$ where if $n_{k} > N_{1}$ we know $| s_{n_{k}} - L | < ϵ / 2$ . And, since $s_{n}$ is Cauchy, we know there is an $N_{2}$ where for any $n, m > N_{2}$ we know $| s_{n} - s_{m} | < ϵ / 2$ .

Let $N = max {N_{1}, N_{2}}$ , and choose any $n > N$ . If $s_{n}$ is in the subsequence, we are good because $n > N_{1}$ and we know for such elements of the subsequence $| s_{n} - L | < ϵ / 2 < ϵ$ . But if $s_{n}$ is not in the subsequence, choose any $m$ such that $m > N$ and $s_{m}$ is in the subsequence, and apply the triangle inequality:

$| s_{n} - L | = | s_{n} - s_{m} + s + m - L | \leq | s_{n} - s_{m} | + | s_{m} - L | \leq \frac{ϵ}{2} + \frac{ϵ}{2} = ϵ$

Where the first inequality is because of the Cauchy condition, and the second is the convergence of the subsequence.

Together these imply the main theorem we advertised.

Theorem 12.1 (Cauchy $⟺$ Convergent) The conditions of being a Cauchy sequence and a convergent sequence are logically equivalent.

If a sequence converges, then every subsequence converges to the same limit (Theorem 11.1). This has a nice application: if you can find any subsequence where it’s easier to compute the values, you can use that subsequence to compute the limit.

Exercise 12.7 Prove directly from the definition of Cauchy: if $s_{n}$ is Cauchy and $s_{n_{k}}$ is a subsequence whose limit is $L$ then $s_{n} \to L$ .

12.1 ★ Properties of Cauchy Sequences

12.2 Cauchy ⟺ Convergent

12.1 $★$ Properties of Cauchy Sequences

12.2 Cauchy $⟺$ Convergent