10 Cauchy Sequences
10.1 Definition
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 10.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 6.4
Example 10.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 10.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 10.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 10.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.
10.2 \(\bigstar\) Properties
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 10.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 7.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 10.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 10.1 (Constant Multiples of Cauchy Sequences) Let \(a_n\) be Cauchy, and \(k\in\RR\) be constant. Then \(ka_n\) is Cauchy.
Proposition 10.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 10.2 (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 10.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 10.3 Show the hypothesis \(b_n\not\to 0\) is necessary in Corollary 10.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.
10.3 Convergence
Now we move on to the main act, where we prove convergence is equivalent to Cauchy by showing an implication in both directions.
Exercise 10.4 (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 10.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 10.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 10.1 (Cauchy \(\iff\) Convergent) The conditions of being a Cauchy sequence and a convergent sequence are logically equivalent.
10.4 Contraction Maps
The cauchy condition (that terms “bunch up”) appears in many natural situations, which makes it a very useful equivalent to convergence. Here we investigate one such instance, when sequences are generated by iterating certain functions.
Definition 10.2 (Contractive Sequence) A sequence \(s_n\) is contractive if there is some positive constant \(k<1\) such that for all \(n\) \[|a_{n+1}-a_n| < k|a_n-a_{n-1}|\]
CONTRACTIVE SEQUENCES (pg 189 in Amazing):
Definition 10.3 (Contraction Map) A function \(f\) is a contraction map if there is some positive constant \(k<1\) such that for all \(x,y\) in the domain of \(f\), \[|f(x)-f(y)|<k|x-y|\]
Proposition 10.5 If \(f\) is a contraction map, iterating \(f\) starting at any point of the domain produces a convergent sequence.
Proof. We prove the existence of a fixed point of \(f\) by constructing a sequence that converges to it. Start by choosing any \(x_0\in\RR\) and set \(\delta = |f(x_0)-x_0|\). We can define a sequence \(x_n\) by iterating \(f\): \(x_{n+1}:=f(x_n)\). Our goal is to show that \(x_n\) is Cauchy by bounding \(|x_m-x_n|\) appropriately. As a starting point, note that as \(f\) is a contraction map we can choose a positive \(k<1\) where \(|f(x)-f(y)|\leq k|x-y|\) for all \(x,y\) and compute
\[\begin{align*} |x_{n+1}-x_n|&=k|f(x_{n})-f(x_{n-1})|\\ &\leq k^2|f(x_{n-1})-f(x_{n-2})|\\ &\leq \cdots\\ &\leq k^n |f(x_0)-x_0|\\ &= k^n\delta \end{align*}\]
This is not the quantity we are really interested in however, we wish to bound \(|x_m-x_n|\). Using the triangle inequality, we can replace this with \(n-m\) bounds of the form above:
\[\begin{align*} |x_m-x_n|&=|x_m-x_{m-1}+x_{m-1}-x_{m-2}+x_{m-2}-\cdots -x_{n+1}+x_{n+1}-x_n|\\ &\leq |x_m-x_{m-1}|+|x_{m-1}-x_{m-2}|+\cdots +|x_{n+1}-x_n|\\ &\leq k^{m-1}\delta + k^{m-2}\delta + \cdots + k^n\delta\\ \end{align*}\]
Simplifying this we can factor out the \(\delta\) to get a sum
\[\delta \left(k^{m-1}+k^{m-2}+\cdots + k^n\right) = \delta \sum_{j=n}^{m-1}k^j=\delta k^n \sum_{j=0}^{m-n-1}k^j\]
The final sum here we may recognize as a geometric series (Exercise 1.6), where
\[\sum_{j=0}^N k^j = \frac{1-k^{N+1}}{1-k}\leq \frac{1}{1-k}\]
Putting this all together, we have managed to bound \(|x_m-x_n|\) by
\[|x_m-x_n|\leq \delta k^n \sum_{j=0}^{m-n-1}k^j\leq \delta k^n\frac{1}{1-k}\]
The numbers \(\delta\) and \(1/(1-k)\) are both constants, and as \(|k|<1\) we know by Example 6.8, \(k^n\to 0\). Thus by the limit laws our bound \(\delta k^n\frac{1}{1-k}\to 0\), which means for every \(\epsilon\) there is some \(N\) where \(n>N\) implies this is less than \(\epsilon\), and hence that \(|x_m-x_n|<\epsilon\). This means the sequence of \(x\)’s is Cauchy, and hence convergent. Thus there is some \(x\in\RR\) with \(x_n\to x\).
Thinking harder about the limit of this sequence proves a rather important theorem in analysis:
Theorem 10.2 (The Contraction Mapping Theorem) Let \(f\colon\RR\to\RR\) be a contraction map. Then there is a unique real number \(x\) such that \(f(x)=x\).
Proof. Starting from any \(x_0\) in the domain, iterating \(f\) produces a sequence converging to some limit point \(x\). Since \(\lim x_n=\lim x_{n+1}=\lim f(x_n)\) we see this same point \(x\) is also the limit of the sequence \(f(x_n)\), so it suffices to prove that \(f(x_n)\to f(x)\). Then since \(f\) is a contraction map, there’s a \(k<1\) where \(|f(x_n)-f(x)|\leq k|x_n-x|\). This second sequence converges to \(0\) by assumption, so \(f(x_n)\to f(x)\) as required (Exercise 6.14). Finally by uniqueness of limits (Theorem 6.1) since \(f(x_n)\to x\) and \(f(x_n)\to f(x)\) we conclude \(x=f(x)\) is a fixed point.
Finally, we check uniqueness. Assume there are two fixed points \(x,y\) with \(x=f(x)\) and \(y=f(y)\). We apply the condition that \(f\) is a contraction map to \(|x-y|\) to get \[|x-y|\leq k|x-y|\] Since \(k\) is strictly less than \(1\), the only solution to this is that \(|x-y|=0\), so \(x=y\) and there is only one fixed point after all.
10.4.1 Applications
Applicaitons: the babylonian procedure for square root of 2 is a contraction map! Others??
Can we show archimedes’ approximates of \(\pi\) are a Cauchy sequence? Archimedes has a recursion process…how does this work?
10.5 Problems
Exercise 10.5 Is the sequence \(s_n=1-\frac{(-1)^n}{n}\) cauchy nor not? Prove your claim.
Exercise 10.6 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?
Exercise 10.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\).