6. \(\limsup\), \(\liminf\), and Cauchy sequences
≪ 5. Midterm 1 Review Solutions | Table of Contents | 7. Rearrangement of Series ≫As mentioned towards the end of discussion two weeks ago, it can be quite hard to prove that a sequence converges straight from the definition without actually knowing what the limit is. This issue led us to formulate an equivalent condition for convergence, which is being a Cauchy sequence.
Definition 1.
A sequence \(\left( a_n \right) _{n=1}^{\infty}\) is a Cauchy sequence if for all \(\epsilon > 0\), there exists some \(N_ \epsilon \) such that for all \(n, m > N _ \epsilon \), \[\left\lvert a_n - a_m \right\rvert < \epsilon .\]
Theorem 2.
A sequence \(\left( a_n \right) _{n=1}^{\infty}\) converges to a limit if and only if it is Cauchy.
This was a great theorem, and it was likely proven in lecture! Convergent sequences being Cauchy is not too difficult to prove (we did it two weeks ago), but the converse is quite a bit more involved. Rather than determining what the limit should have been, we defined two other limiting quantities, the \(\limsup\) and the \(\liminf\).
Definition 3.
Given a sequence of real numbers \(\left( a_n \right) _{n=1}^{\infty}\), we define \[\limsup_{n\to\infty} a_n = \lim _{N\to\infty} \left( \sup \left\lbrace a_n : n \geq N \right\rbrace \right) \] and \[\liminf _{n\to\infty} a_n = \lim _{N\to\infty} \left( \inf \left\lbrace a_n : n \geq N \right\rbrace \right). \]
In addition to being helpful in showing the equivalence between convergence and being Cauchy, the \(\limsup\) and \(\liminf\) are frequently employed when analysing sequences whose convergence is unknown. The \(\limsup\) and \(\liminf\) of a sequence are always guaranteed to exist (or be infinite, if you want to be pedantic), as they are limits of monotone sequences.
While the “limit of suprema of the tail of a sequence” is clunky and difficult to work with directly, there is an alternative characterisation of what exactly the \(\limsup\) (and likewise \(\liminf\)) is:
Proposition 4.
Let \(\left( a_n \right) _{n=1}^{\infty}\) be a sequence of real numbers. \(M = \limsup _{n\to\infty} a_n\) if and only if for every \(\epsilon > 0\),
- there exists some \(N_ \epsilon \) such that for all \(n > N_ \epsilon \), \(a_n < M + \epsilon \), and
- there exist infinitely many \(n\) for which \(a_n > M - \epsilon \).
I had given a (slightly erroneous) version of this statement as an exercise in preparation for the midterm; you can find a proof of it in the solutions.
Remark 5. The Completeness Axiom
Recall that one of the axioms we had assumed about the real numbers was that every bounded set has a least upper bound. This fact is critical to proving the Cauchy sequences are the same as converging sequences, particularly when figuring things out about \(\limsup\)’s and \(\liminf\)’s.
This “completeness axiom” is actually logically equivalent to the statement “every Cauchy sequence converges”. That is to say, if we had assumed that every Cauchy sequence converges as our “completeness axiom” rather than assuming that suprema of bounded sets always exist, we could prove the latter!
We can use this to do something highly nontrivial: we can prove some convergence theorems from AP Calculus or Math 31B about series. Recall that given a sequence of real numbers \(\left( a_n \right)\), we can define the partial sums \(S_N = \sum _{n=1}^{N} a_n\) and the series \[\sum _{n=1}^{\infty} a_n = \lim _{N\to\infty} S_N,\] if the limit exists. Determining whether or not these series converge was of central importance to calculus (e.g. Taylor series), but proving convergence straight from the definitions is generally speaking not a great idea. So, convergence tests were born, such as:
Theorem 6. Ratio test
Let \(\left( a_n \right)\) be a sequence of real numbers, and let \[\begin{align*} M = \limsup _{n\to\infty} \frac{\left\lvert a _{n+1} \right\rvert}{ \left\lvert a_n \right\rvert} && \textrm{and} && L = \liminf _{n\to\infty} \frac{\left\lvert a _{n+1} \right\rvert}{\left\lvert a_n \right\rvert}.\end{align*}\] Then \(\sum _{n=1}^{\infty} a_n\) exists if \(M < 1\), and \(\sum _{n=1}^{\infty} a_n\) does not exist if \(L > 1\).
(If neither is true, then the theorem is inconclusive. If \(a_n = 0\), then the fraction is treated as \(+\infty\). )
The idea is as follows: we’ll show that if \(M < 1\), then \(a_n\) can eventually be controlled in magnitude by a converging geometric series. This will enable us to show that the partial sums \(S_N\) form a Cauchy sequence, and in particular, conclude that \(S_N\) converges to some limit.
On the other hand, if \(L > 1\), then \(a_n\) will eventually be larger in magnitude than a diverging geometric series. We can then show that the partial sums do not form a Cauchy sequence, hence do not converge to a limit.
Notice that we are not assuming that there is a limit to these sequences at all, and in fact we don’t really have a way of knowing what the limit should even be. This essentially prevents us from arguing directly that the series will exist.
I’ll only provide a proof of the first claim, and I’ll leave a proof of the second claim as an exercise.
Proof
First, suppose \(M < 1\). Let \(r = \frac{1+M}{2}\), and note that \(M < r < 1\). By the earlier proposition, there exists some \(N’\) such that for all \(n > N’\), \[\frac{\left\lvert a _{n+1} \right\rvert}{ \left\lvert a_n \right\rvert} < r \implies \left\lvert a _{n+1} \right\rvert < r \left\lvert a_n \right\rvert. \] Either by induction or by spamming this inequality a million times, one gets for all \(n > N’\) that \[\left\lvert a_n \right\rvert < r ^{n-N’} \left\lvert a _{N’} \right\rvert.\] We’ll use this to show that the partial sums \(S_N\) form a Cauchy sequence. Fix \(\epsilon > 0\), and let \(N _ \epsilon \geq N’\) to be determined later. (I could use powers of foresight to determine \(N_ \epsilon \), but this is difficult.) We have for any \(n> m > N_ \epsilon \) that \[\begin{align*} \left\lvert S_n - S_m \right\rvert &= \left\lvert \sum _{k=n}^{m-1}a_k \right\rvert \\ & \leq \sum _{k=n}^{m-1} \left\lvert a_k \right\rvert \\ & \leq \sum _{k=n}^{m-1} r ^{k-N’} \left\lvert a _{N’} \right\rvert \\ & \leq \frac{\left\lvert a _{N’} \right\rvert}{1 - r} \cdot r ^{n - N’} \\ & \leq \frac{\left\lvert a _{N’} \right\rvert}{1-r} \cdot r ^{N_ \epsilon - N’}. \end{align*}\] The first inequality is the triangle inequality; the second is the term-by-term inequality from above; the third is from the geometric series formula; and the fourth is because \(r^n < r ^{N_ \epsilon }\), for \(r < 1\) and \(n > N_ \epsilon \).
When \(N_ \epsilon \) is very, very large depending on \(\epsilon \), one can make this final quantity smaller than \(\epsilon \). We conclude that the sequence of partial sums is a Cauchy sequence, hence it must converge to a limit. \(\square\)
Exercise 7. The Root Test
Let \(\left( a_n \right)\) be a sequence of real numbers, and define \[\begin{align*} M = \limsup _{n\to\infty} \left\lvert a_n \right\rvert ^{\frac{1}{n}} && \textrm{and} && L = \liminf _{n\to\infty} \left\lvert a_n \right\rvert ^{\frac{1}{n}}.\end{align*}\] Show that if \(M < 1\), then \(\sum _{n=1}^{\infty} a_n\) exists, and if \(L> 1\), then \(\sum _{n=1}^{\infty} a_n\) does not exist.
Hint
Exercise 8. The Contraction Mapping Principle
Let \(f : \left[ 0, 1 \right] \to \left[ 0, 1 \right]\) be a differentiable function such that \(\left\lvert f’(x) \right\rvert \leq \frac{1}{2}\) for all \(x\in \left[ 0,1 \right]\).
- Use the mean value theorem to show that \(\left\lvert f(x) - f(y) \right\rvert \leq \frac{1}{2}\left\lvert x-y \right\rvert\) for all \(x, y\in \left[ 0, 1 \right]\).
- Define the sequence \(x_1 = 1\), \(x _{n} = f \left( x _{n-1} \right)\) for \(n \geq 1\). Show that \(\left( x_n \right)\) is a Cauchy sequence.
- Conclude that \(x_n\) converges to a limit. What do you think this limit represents?