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 \(\epsilon>0\) there is an \(N\) where if \(n>N\) then \(|a_n-a_{n+1}|<\epsilon\)
Unfortunately this doesn’t quite seem to work: perhaps surprisingly, it is possible for consecutive terms of a sequence to all get within \(\epsilon\) 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 \(\epsilon>0\) there is an \(N\) where \(n>N\) implies \(|\sqrt{n}-\sqrt{n+1}|<\epsilon\), but nonetheless \(a_n\) diverges (to infinity).
Proof. We can estimate the difference between consecutive terms with some algebra: \[\begin{align*} \sqrt{n+1}-\sqrt{n} &= \left(\sqrt{n+1}-\sqrt{n}\right)\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{align*}\] Thus for any \(\epsilon>0\) we can just take \(N=\frac{1}{\epsilon^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}{\epsilon^2}}}=\epsilon\]
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}+\cdots+\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 \(\epsilon>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 \(\epsilon>0\) there is a threshold past which any two terms of the sequence differ from one another by at most \(\epsilon\). As a logic sentence, \[\forall\epsilon>0\,\,\exists N\,\,\forall m,n>N\,\,|s_n-s_m|<\epsilon\]
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\) \[\left|\frac{1}{n}-\frac{1}{m}\right|<\left|\frac{1}{n}-0\right|=\frac{1}{n}\] And we already know that for any \(\epsilon\) we can choose \(N\) with \(n>N\) implying \(1/n<\epsilon\).
Example 12.4 (Cauchy Sequences: A Nonexample) The sequence \(s_n=1,0,1,0,1,0\ldots\) is not Cauchy, as the difference between any two consecutive terms is \(1\). Thus for \(\epsilon=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 \(\bigstar\) 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\NN\).
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 \(\epsilon=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,\ldots, a_N, a_{N+1}-1\}\] \[U=\max\{a_1,a_2,\ldots, 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 \(\epsilon>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|<\epsilon/2\) and \(|b_n-b_m|<\epsilon/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{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon\]
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\RR\) be constant. Then \(ka_n\) is Cauchy.
Proposition 12.3 (Products of Cauchy Sequences) Let \(a_n,b_n\) be Cauchy. Then \(s_n=a_nb_n\) is a cauchy sequence.
First, some scratch work: we are going to want to work with the condition \(|s_n-s_m|= |a_nb_n-a_mb_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{align*} |a_nb_n-a_mb_m|&=|a_nb_n+(a_nb_m-a_nb_m)-a_mb_m|\\ &=|(a_nb_n-a_nb_m)+(a_nb_m-a_mb_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{align*}\]
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 \(\epsilon>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{\epsilon}{2M}\hspace{1cm}|b_n-b_m|<\frac{\epsilon}{2M}\] 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{\epsilon}{2M}=\frac{\epsilon}{2}\hspace{1cm} |b_m||a_n-a_m|\leq M\frac{\epsilon}{2M}=\frac{\epsilon}{2}\] Together, this means their sum is less than \(\epsilon\), and from our scratch work we see their sum is already an upper bound for the quantity we are actually interested in: \[|a_nb_n-a_mb_m|\leq |a_n||b_n-b_m|+|b_m||a_n-a_m|\leq \epsilon\]
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\not\to 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 \(\iff\) 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 \(\epsilon>0\). Since \(s_{n_k}\to L\) there exists an \(N_1\) where if \(n_k>N_1\) we know \(|s_{n_k}-L|<\epsilon/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|<\epsilon/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|<\epsilon/2<\epsilon\). 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{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon\]
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 \(\iff\) 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\).