The two lists of rationals in Example 1.3 close in on \(\sqrt2\) . The numbers \(1/n\) shrink towards \(0\) . The decimal truncations \(3,\ 3.1,\ 3.14,\ 3.141,\dots\) home in on something. Each of these sentences uses a verb of motion to describe a list of fixed numbers, and none of them says how close, or by when. The definition of a limit replaces the motion by a guarantee: name any tolerance, and from some point on every term meets it.

That definition answers one question and raises another. To check it you must already know the limit. But the decimal truncations above are given with no candidate limit attached, and a recursively defined sequence usually arrives the same way. Can one decide that a sequence converges by looking only at its terms? In \(\mathbb R\) the answer is yes, and the answer turns out to be the completeness axiom wearing different clothes.

2.1 The definition and how to use it

A sequence of real numbers is a function from \(\mathbb N\) to \(\mathbb R\) ; we write its value at \(n\) as \(x_n\) and the whole sequence as \((x_n)\) .

Read the definition as a challenge and a response. A sceptic names a tolerance \(\varepsilon\) . You must answer with an index \(N\) , which is allowed to depend on \(\varepsilon\) , after which every term lies in the band from \(L-\varepsilon\) to \(L+\varepsilon\) . A smaller \(\varepsilon\) will usually need a larger \(N\) ; what matters is that some \(N\) exists for each \(\varepsilon\) . Only finitely many terms, those with \(n<N\) , can lie outside the band, and what they do is irrelevant.

Example 2.1: An explicit index for a given tolerance

Let \(x_n=(2n+1)/(n+3)\) . We claim \(x_n\to 2\) .

Scratch work. Compute the distance to the proposed limit:

\[ \lvert x_n-2\rvert=\left\lvert\frac{2n+1-2(n+3)}{n+3}\right\rvert=\frac{5}{n+3}. \]

This is less than \(\varepsilon\) exactly when \(n+3>5/\varepsilon\) .

Proof. Let \(\varepsilon>0\) . By the Archimedean property choose \(N\in\mathbb N\) with \(N>5/\varepsilon\) . If \(n\ge N\) , then \(n+3>5/\varepsilon\) , so \(\lvert x_n-2\rvert=5/(n+3)<\varepsilon\) .

For the tolerance \(\varepsilon=0.01\) the exact condition is \(n+3>500\) , so the smallest index that works is \(N=498\) : indeed \(\lvert x_{498}-2\rvert=5/501\approx 0.00998\) , while \(\lvert x_{497}-2\rvert=5/500=0.01\) is not less than \(0.01\) . The proof did not need the smallest \(N\) ; any \(N\) beyond \(5/\varepsilon\) is acceptable, and choosing a generous one is often what keeps a proof short.

Theorem 2.2 (uniqueness of the limit). A sequence converges to at most one number.

Proof. Suppose \(x_n\to L\) and \(x_n\to L'\) with \(L\ne L'\) . Put \(\varepsilon=\lvert L-L'\rvert/2>0\) . There are \(N_1\) and \(N_2\) with \(\lvert x_n-L\rvert<\varepsilon\) for \(n\ge N_1\) and \(\lvert x_n-L'\rvert<\varepsilon\) for \(n\ge N_2\) . For an \(n\) larger than both,

\[ \lvert L-L'\rvert\le\lvert L-x_n\rvert+\lvert x_n-L'\rvert<2\varepsilon=\lvert L-L'\rvert, \]

which is absurd.

To prove divergence one needs the negation of Definition 2.1, and it pays to write it out once. The statement “\((x_n)\) does not converge to \(L\) ” reads: there is an \(\varepsilon_0>0\) such that for every \(N\) there is some \(n\ge N\) with \(\lvert x_n-L\rvert\ge\varepsilon_0\) . One bad tolerance suffices, but it must defeat every \(N\) .

2.2 Limits and algebra

The converse fails, as Example 2.2 shows. Boundedness is necessary for convergence and far from sufficient; Section 2.4 says exactly how much it buys.

The proof of (c) contains a move worth isolating: before dividing by \(y_n\) we used convergence once, with the fixed tolerance \(\lvert y\rvert/2\) , to keep \(y_n\) away from \(0\) . Using the definition with a specific convenient \(\varepsilon\) to gain control, and then again with the given \(\varepsilon\) , is a standard two-stage argument.

Two cautions. In (a) the hypotheses need only hold from some index on, since finitely many terms never affect a limit. And strict inequalities are not preserved: \(1/n>0\) for every \(n\) , yet the limit is \(0\) , not a positive number. Part (b) proves convergence of \((w_n)\) ; it does not assume it.

2.3 Monotone sequences

This is the first theorem that produces a limit without being told what it is. Completeness supplies the candidate, exactly as it supplied \(\sqrt2\) in Theorem 1.11. Over \(\mathbb Q\) the theorem is false: the increasing rationals \(1,\,4/3,\,7/5,\,24/17,\dots\) of Example 1.3 are bounded above and have no rational limit.

2.4 Subsequences and the Bolzano–Weierstrass theorem

A subsequence selects infinitely many terms and keeps them in their original order. Note that \(n_k\ge k\) for every \(k\) , by induction.

The contrapositive is the most convenient divergence test there is: a sequence with two subsequences converging to different limits diverges.

Bounded sequences need not converge, but they cannot avoid having convergent subsequences. The proof rests on a combinatorial fact with no hypotheses at all.

2.5 Cauchy sequences

We return to the question from the chapter opening: how can one recognise convergence without knowing the limit? The idea, due to Cauchy, is that terms which are all close to a common limit must be close to each other.

The definition mentions no limit. It compares every pair of terms beyond \(N\) , not just neighbours.

Trace the dependence backwards: the Cauchy criterion rests on Bolzano–Weierstrass, which rests on monotone convergence, which rests on the completeness axiom. The chain can be closed. In an ordered field with the Archimedean property, each of the following implies the others: the supremum property of Definition 1.7; the monotone convergence theorem; the nested interval theorem; the Bolzano–Weierstrass theorem; the Cauchy criterion. Exercise 16 proves one of the return implications. This is why “\(\mathbb R\) is complete” is often taken to mean that every Cauchy sequence converges, and that is the form in which completeness will be carried to metric spaces in Chapter 4. Over \(\mathbb Q\) the criterion fails: the rationals \(1,\,4/3,\,7/5,\dots\) of Example 1.3 form a Cauchy sequence, since they converge in \(\mathbb R\) , but they have no limit in \(\mathbb Q\) .

2.6 Limit superior and limit inferior

A bounded divergent sequence still has a largest and a smallest subsequential limit. They can be defined without mentioning subsequences, and they measure how far the sequence is from converging.

The limits exist. The tail \(\{x_k:k\ge n+1\}\) is a subset of \(\{x_k:k\ge n\}\) , so \(u_{n+1}\le u_n\) and \(\ell_{n+1}\ge\ell_n\) by Proposition 1.15(a) and its mirror image for infima. Both sequences are bounded because \((x_n)\) is, and Theorem 2.9 applies.

For the sequence of Example 2.5 the tail suprema are \(u_n=1+1/n\) when \(n\) is even and \(u_n=1+1/(n+1)\) when \(n\) is odd, so \(\limsup x_n=1\) ; similarly \(\liminf x_n=-1\) . The gap \(U-\Lambda=2\) is the size of the oscillation that survives in every tail.

One more piece of vocabulary. We write \(x_n\to+\infty\) if for every real \(M\) there is an \(N\) with \(x_n>M\) for all \(n\ge N\) , and \(x_n\to-\infty\) analogously. Such a sequence diverges; the notation records the manner of divergence and does not make \(\infty\) a number. For a sequence not bounded above we set \(\limsup x_n=+\infty\) , and for one not bounded below \(\liminf x_n=-\infty\) .

With limits of sequences in hand, the next chapter adds infinitely many numbers. A series is nothing more than the sequence of its partial sums, so every theorem here has an echo there, and the Cauchy criterion in particular becomes the main working tool.

Exercises

1. Using only Definition 2.1, prove that \((3n-1)/(n+2)\to 3\) , and find the smallest \(N\) that works for \(\varepsilon=0.01\) .

   Solution

   Scratch work. For \(x_n=(3n-1)/(n+2)\) ,

   \[ \lvert x_n-3\rvert=\left\lvert\frac{3n-1-3(n+2)}{n+2}\right\rvert=\frac{7}{n+2}. \]

   Proof. Let \(\varepsilon>0\) . By the Archimedean property choose \(N\in\mathbb N\) with \(N>7/\varepsilon\) . For \(n\ge N\) we have \(n+2>7/\varepsilon\) , hence \(\lvert x_n-3\rvert=7/(n+2)<\varepsilon\) . So \(x_n\to 3\) .

   The smallest index for \(\varepsilon=0.01\) . The inequality \(7/(n+2)<0.01\) is equivalent to \(n+2>700\) , that is \(n>698\) . Because \(7/(n+2)\) decreases as \(n\) grows, every \(n\ge 699\) works and \(n=698\) does not: \(\lvert x_{698}-3\rvert=7/700=0.01\) exactly, which is not less than \(0.01\) , while \(\lvert x_{699}-3\rvert=7/701\approx 0.009986\) . The smallest \(N\) is \(N=699\) .

2. Write out, with all quantifiers, the statement “the sequence \((x_n)\) diverges” (it must mention every candidate limit \(L\) ). Use it to prove that \(x_n=n\) diverges without quoting Proposition 2.3.

   Answer

   “For every real \(L\) there is an \(\varepsilon_0>0\) such that for every \(N\in\mathbb N\) there is an \(n\ge N\) with \(\lvert x_n-L\rvert\ge\varepsilon_0\) .” For \(x_n=n\) : given \(L\) , take \(\varepsilon_0=1\) . Given \(N\) , choose by the Archimedean property an \(n\ge N\) with \(n>\lvert L\rvert+1\) . Then \(\lvert n-L\rvert\ge n-\lvert L\rvert>1\) .

3. Prove that \(x_n\to x\) implies \(\lvert x_n\rvert\to\lvert x\rvert\) . Show by example that the converse is false in general, and prove that it is true when \(x=0\) .

   Solution

   The implication. Let \(x_n\to x\) and \(\varepsilon>0\) . Choose \(N\) with \(\lvert x_n-x\rvert<\varepsilon\) for \(n\ge N\) . By the second inequality of Proposition 1.4,

   \[ \bigl\lvert\,\lvert x_n\rvert-\lvert x\rvert\,\bigr\rvert\le\lvert x_n-x\rvert<\varepsilon\qquad\text{for }n\ge N . \]

   Hence \(\lvert x_n\rvert\to\lvert x\rvert\) .

   The converse fails. For \(x_n=(-1)^n\) we have \(\lvert x_n\rvert=1\) for all \(n\) , so \(\lvert x_n\rvert\to 1\) , but \((x_n)\) diverges by Example 2.2. Absolute values forget the sign, and the sign can oscillate.

   The converse holds when \(x=0\) . Suppose \(\lvert x_n\rvert\to 0\) . The quantity that the definition of \(x_n\to 0\) asks us to make small is \(\lvert x_n-0\rvert=\lvert x_n\rvert\) , and the quantity that \(\lvert x_n\rvert\to 0\) makes small is \(\bigl\lvert\lvert x_n\rvert-0\bigr\rvert=\lvert x_n\rvert\) . They are the same number, so the two statements are literally the same statement.

4. Prove that if \(x_n\to 0\) and \((y_n)\) is bounded, then \(x_ny_n\to 0\) , and explain why Theorem 2.4(b) cannot be quoted for this. Deduce that \(\sin(n)/n\to 0\) .

   Hint

   Let \(\lvert y_n\rvert\le M\) with \(M>0\) . Then \(\lvert x_ny_n\rvert\le M\lvert x_n\rvert\) ; given \(\varepsilon\) , choose \(N\) with \(\lvert x_n\rvert<\varepsilon/M\) . Theorem 2.4(b) needs both sequences to converge, and \((y_n)\) is only assumed bounded. For the last part take \(x_n=1/n\) and \(y_n=\sin n\) , which is bounded by \(1\) ; whether \(\sin n\) converges is irrelevant.

5. Find each limit and justify it with the theorems of Section 2.2: (a) \((4n^2-n)/(2n^2+3)\) ; (b) \(\sqrt{n+1}-\sqrt n\) ; (c) \((2^n+3^n)^{1/n}\) , for which you may use that \(c^{1/n}\to 1\) for \(c>0\) .

   Answer

   (a) \(2\) : divide numerator and denominator by \(n^2\) to get \((4-1/n)/(2+3/n^2)\) and apply Theorem 2.4. (b) \(0\) : the expression equals \(1/(\sqrt{n+1}+\sqrt n)\) , which lies between \(0\) and \(1/\sqrt n\) , and \(1/\sqrt n<\varepsilon\) once \(n>1/\varepsilon^2\) ; squeeze. (c) \(3\) : since \(3^n\le 2^n+3^n\le 2\cdot 3^n\) , we get \(3\le(2^n+3^n)^{1/n}\le 3\cdot 2^{1/n}\) , and \(2^{1/n}\to 1\) ; squeeze.

6. Prove that \(n^{1/n}\to 1\) by writing \(n^{1/n}=1+h_n\) with \(h_n\ge 0\) and using the binomial inequality \((1+h)^n\ge\tfrac12n(n-1)h^2\) for \(h\ge 0\) and \(n\ge 2\) . Deduce that \(c^{1/n}\to 1\) for every \(c>0\) .

   Solution

   For \(n\ge 1\) we have \(n^{1/n}\ge 1\) , since a positive number less than \(1\) has \(n\) th power less than \(1\) . So \(h_n=n^{1/n}-1\ge 0\) .

   For \(h\ge 0\) and \(n\ge 2\) the binomial theorem expresses \((1+h)^n\) as a sum of nonnegative terms, one of which is \(\binom n2h^2=\tfrac12n(n-1)h^2\) . Hence \((1+h)^n\ge\tfrac12n(n-1)h^2\) . Apply this with \(h=h_n\) :

   \[ n=(1+h_n)^n\ge\tfrac12n(n-1)h_n^2,\qquad\text{so}\qquad 0\le h_n\le\sqrt{\frac{2}{n-1}}\quad(n\ge 2). \]

   Given \(\varepsilon>0\) , the bound \(\sqrt{2/(n-1)}\) is less than \(\varepsilon\) as soon as \(n>1+2/\varepsilon^2\) . So \(h_n\to 0\) by the squeeze theorem, and \(n^{1/n}=1+h_n\to 1\) .

   Now let \(c>0\) . If \(c\ge 1\) , then for every \(n\ge c\) we have \(1\le c^{1/n}\le n^{1/n}\) , and the squeeze theorem gives \(c^{1/n}\to 1\) . If \(0<c<1\) , then \(1/c>1\) and \(c^{1/n}=1/(1/c)^{1/n}\to 1/1=1\) by the quotient law.

7. Let \(x_1=1\) and \(x_{n+1}=\sqrt{2+x_n}\) . Prove that the sequence is increasing and bounded above by \(2\) , and find its limit, taking care to justify the passage to the limit in the recursion.

   Solution

   Bounded. We show \(0<x_n\le 2\) by induction. \(x_1=1\) . If \(0<x_n\le 2\) then \(2<2+x_n\le 4\) , so \(x_{n+1}=\sqrt{2+x_n}\) satisfies \(0<x_{n+1}\le 2\) , because the square root is increasing on positive numbers (Exercise 1.2).

   Increasing. Compare squares:

   \[ x_{n+1}^2-x_n^2=2+x_n-x_n^2=(2-x_n)(1+x_n)\ge 0, \]

   since \(0<x_n\le 2\) . As both terms are positive, \(x_{n+1}\ge x_n\) .

   Convergence. By the monotone convergence theorem \(x_n\to L\) for some \(L\) , and \(1\le L\le 2\) by Theorem 2.5.

   The limit. To avoid assuming anything about limits of square roots, square the recursion: \(x_{n+1}^2=2+x_n\) . The left side converges to \(L^2\) by the product law, because \((x_{n+1})\) also converges to \(L\) ; the right side converges to \(2+L\) . By uniqueness of limits \(L^2=2+L\) , so \((L-2)(L+1)=0\) . Since \(L\ge 1\) , we conclude \(L=2\) .

   Numerically \(x_2=\sqrt3\approx 1.7321\) , \(x_3\approx 1.9319\) , \(x_4\approx 1.9829\) , \(x_5\approx 1.9957\) .

8. Show that \(a_n=(1+1/n)^n\) is increasing and that \(a_n<3\) for all \(n\) , so that the sequence converges. (Expand by the binomial theorem and compare the terms of \(a_n\) and \(a_{n+1}\) one by one.)

   Hint

   By the binomial theorem

   \[ a_n=\sum_{k=0}^{n}\frac{1}{k!}\Bigl(1-\frac1n\Bigr)\Bigl(1-\frac2n\Bigr)\cdots\Bigl(1-\frac{k-1}{n}\Bigr). \]

   Each factor \(1-j/n\) increases when \(n\) is replaced by \(n+1\) , and \(a_{n+1}\) has one more positive term; so \(a_n<a_{n+1}\) . Each product is at most \(1\) , so \(a_n\le\sum_{k=0}^n1/k!\) ; bound this using \(k!\ge 2^{k-1}\) and the finite geometric sum.

9. A student is given \(x_1=1\) , \(x_{n+1}=3x_n-1\) and writes: “Let \(L\) be the limit. Then \(L=3L-1\) , so the sequence converges to \(1/2\) .” Compute the first five terms, say what is wrong with the argument, and say what the computation \(L=3L-1\) does establish.

   Answer

   The terms are \(1,2,5,14,41\) . Since \(x_{n+1}-x_n=2x_n-1\ge 1\) whenever \(x_n\ge 1\) , the sequence increases by at least \(1\) per step and is unbounded, hence divergent. The argument assumed that a limit exists. What \(L=3L-1\) establishes is conditional: if a sequence satisfying the recursion converges, its limit is \(1/2\) . That happens only for the constant sequence started at \(x_1=1/2\) .

10. For each \(n\) let \(r_n\in\{0,1,2\}\) be the remainder of \(n\) on division by \(3\) , and let \(x_n=r_n+1/n\) . Find all subsequential limits of \((x_n)\) , and find \(\limsup x_n\) and \(\liminf x_n\) .

    Answer

    Along \(n=3k\) , \(x_n=1/(3k)\to 0\) ; along \(n=3k+1\) , \(x_n\to 1\) ; along \(n=3k+2\) , \(x_n\to 2\) . A convergent subsequence contains infinitely many indices from one of the three classes, so its limit is \(0\) , \(1\) , or \(2\) . Hence the subsequential limits are exactly \(0,1,2\) , with \(\limsup x_n=2\) and \(\liminf x_n=0\) .

11. Prove that \(x_n\to L\) if and only if every subsequence of \((x_n)\) has a further subsequence that converges to \(L\) .

    Solution

    If \(x_n\to L\) . By Proposition 2.11 every subsequence converges to \(L\) . A sequence is a subsequence of itself, so each subsequence has a further subsequence, namely itself, converging to \(L\) .

    Conversely, we prove the contrapositive. Suppose \((x_n)\) does not converge to \(L\) . By the negation of Definition 2.1 there is \(\varepsilon_0>0\) such that for every \(N\) some \(n\ge N\) has \(\lvert x_n-L\rvert\ge\varepsilon_0\) . Use this repeatedly: choose \(n_1\) with \(\lvert x_{n_1}-L\rvert\ge\varepsilon_0\) ; then, applying the statement with \(N=n_1+1\) , choose \(n_2>n_1\) with \(\lvert x_{n_2}-L\rvert\ge\varepsilon_0\) ; and so on. This produces a subsequence \((x_{n_k})\) all of whose terms are at distance at least \(\varepsilon_0\) from \(L\) . Every further subsequence of it has the same property, so none of them converges to \(L\) : the tolerance \(\varepsilon_0\) is never met. Thus there is a subsequence with no further subsequence converging to \(L\) , which is the negation of the condition.

12. Prove directly from Definition 2.14, without mentioning any limit, that \(x_n=(n+1)/n\) is a Cauchy sequence.

    Hint

    \(\lvert x_n-x_m\rvert=\lvert 1/n-1/m\rvert\) . For \(m,n\ge N\) both \(1/n\) and \(1/m\) lie in the interval \((0,1/N]\) , so their distance is less than \(1/N\) . Given \(\varepsilon\) , choose \(N\ge 1/\varepsilon\) .

13. Let \(s_n=1+1/2+\cdots+1/n\) . Show that \(s_{2n}-s_n\ge 1/2\) for every \(n\) , and conclude that \((s_n)\) is not Cauchy although \(s_{n+1}-s_n\to 0\) .

    Solution

    For every \(n\) ,

    \[ s_{2n}-s_n=\frac{1}{n+1}+\frac{1}{n+2}+\cdots+\frac{1}{2n}. \]

    There are \(n\) terms and each is at least the last one, \(1/(2n)\) . Hence \(s_{2n}-s_n\ge n\cdot\frac{1}{2n}=\frac12\) .

    Now suppose \((s_n)\) were Cauchy and apply Definition 2.14 with \(\varepsilon=1/2\) : there would be \(N\) with \(\lvert s_m-s_n\rvert<1/2\) for all \(m,n\ge N\) . But \(n=N\) and \(m=2N\) are both at least \(N\) and \(s_{2N}-s_N\ge 1/2\) . So \((s_n)\) is not Cauchy, and by the Cauchy criterion it diverges; being increasing, it is unbounded.

    Meanwhile \(s_{n+1}-s_n=1/(n+1)\to 0\) . Consecutive differences that tend to zero do not make a sequence Cauchy. For instance \(s_{20}-s_{10}\approx 0.6688\) , comfortably above \(1/2\) , although the individual steps between them are all at most \(1/11\) .

14. Let \(x_1=1\) and \(x_{n+1}=1+1/x_n\) . Show that \(3/2\le x_n\le 2\) for \(n\ge 2\) , that the sequence is contractive with constant \(4/9\) from the second term on, and that its limit is \((1+\sqrt5)/2\) .

    Solution

    The terms are \(x_1=1\) , \(x_2=2\) , \(x_3=3/2\) , \(x_4=5/3\) , \(x_5=8/5\) .

    Bounds. \(x_2=2\) lies in \([3/2,2]\) . If \(3/2\le x_n\le 2\) , then \(1/2\le 1/x_n\le 2/3\) , so \(3/2\le x_{n+1}\le 5/3\le 2\) . By induction \(3/2\le x_n\le 2\) for all \(n\ge 2\) .

    Contraction. For \(n\ge 2\) ,

    \[ \lvert x_{n+2}-x_{n+1}\rvert=\left\lvert\frac{1}{x_{n+1}}-\frac{1}{x_n}\right\rvert=\frac{\lvert x_{n+1}-x_n\rvert}{x_{n+1}x_n}\le\frac49\,\lvert x_{n+1}-x_n\rvert, \]

    because \(x_nx_{n+1}\ge(3/2)^2=9/4\) .

    Convergence and limit. Proposition 2.17 applies to the sequence \(x_2,x_3,x_4,\dots\) with \(c=4/9\) , so it converges; a sequence and the same sequence with its first term removed have the same limit. Call the limit \(L\) ; then \(3/2\le L\le 2\) by Theorem 2.5. Letting \(n\to\infty\) in \(x_{n+1}=1+1/x_n\) , with the quotient law justified because \(L\ne 0\) , gives \(L=1+1/L\) , that is \(L^2-L-1=0\) . The roots are \((1\pm\sqrt5)/2\) , and only \(L=(1+\sqrt5)/2\approx 1.618034\) lies in \([3/2,2]\) .

    The terms are ratios of consecutive Fibonacci numbers; \(x_{10}=89/55\approx 1.618182\) .

15. Give a proof of the Bolzano–Weierstrass theorem by bisection: enclose the sequence in \([a,b]\) , repeatedly halve, always keeping a half that contains infinitely many terms, and use the nested interval theorem to produce the limit of a subsequence.

    Hint

    Let \(I_1=[a,b]\) contain every term. If \(I_k\) contains \(x_n\) for infinitely many \(n\) , at least one of its two closed halves does too; call it \(I_{k+1}\) . The lengths are \((b-a)/2^{k-1}\) , with infimum \(0\) , so the nested interval theorem gives a single common point \(x\) . Choose indices \(n_1<n_2<\cdots\) with \(x_{n_k}\in I_k\) , which is possible because each \(I_k\) contains infinitely many terms. Then \(\lvert x_{n_k}-x\rvert\le(b-a)/2^{k-1}\) .

16. Assume only the Archimedean property and the statement “every Cauchy sequence of real numbers converges”. Prove from these that every increasing sequence that is bounded above converges.

    Solution

    Let \((x_n)\) be increasing with \(x_n\le B\) for all \(n\) . We show that \((x_n)\) is Cauchy; the assumed statement then gives convergence.

    Suppose it is not Cauchy. Then there is \(\varepsilon_0>0\) such that for every \(N\) there are indices \(m>n\ge N\) with \(\lvert x_m-x_n\rvert\ge\varepsilon_0\) ; since the sequence is increasing, this says \(x_m-x_n\ge\varepsilon_0\) .

    Apply this with \(N=1\) to get \(n_1<m_1\) with \(x_{m_1}\ge x_{n_1}+\varepsilon_0\ge x_1+\varepsilon_0\) . Apply it with \(N=m_1\) to get \(m_1\le n_2<m_2\) with \(x_{m_2}\ge x_{n_2}+\varepsilon_0\ge x_{m_1}+\varepsilon_0\ge x_1+2\varepsilon_0\) , where \(x_{n_2}\ge x_{m_1}\) by monotonicity. Continuing, for every \(k\) we find an index \(m_k\) with

    \[ x_{m_k}\ge x_1+k\varepsilon_0 . \]

    By the Archimedean property there is \(k\) with \(k>(B-x_1)/\varepsilon_0\) , and for that \(k\) we get \(x_{m_k}>B\) , contradicting the bound. Hence \((x_n)\) is Cauchy and therefore converges.

    The Archimedean property was used exactly once, to turn “infinitely many jumps of size \(\varepsilon_0\) ” into “arbitrarily large”.

17. Let \(x_n=(-1)^n(2+3/n)\) . Compute \(u_n=\sup\{x_k:k\ge n\}\) and \(\ell_n=\inf\{x_k:k\ge n\}\) for each \(n\) , and hence find \(\limsup x_n\) and \(\liminf x_n\) .

    Answer

    For even \(n\) , \(x_n=2+3/n\) , decreasing towards \(2\) ; for odd \(n\) , \(x_n=-(2+3/n)\) , increasing towards \(-2\) . Hence \(u_n=2+3/n\) for even \(n\) and \(u_n=2+3/(n+1)\) for odd \(n\) ; \(\ell_n=-(2+3/n)\) for odd \(n\) and \(\ell_n=-(2+3/(n+1))\) for even \(n\) . So \(\limsup x_n=2\) and \(\liminf x_n=-2\) .

18. For bounded sequences \((x_n)\) and \((y_n)\) prove that \(\limsup(x_n+y_n)\le\limsup x_n+\limsup y_n\) , and give an example in which the inequality is strict.

    Solution

    Write \(u_n=\sup\{x_k:k\ge n\}\) , \(v_n=\sup\{y_k:k\ge n\}\) , and \(w_n=\sup\{x_k+y_k:k\ge n\}\) . For every \(k\ge n\) we have \(x_k\le u_n\) and \(y_k\le v_n\) , so \(x_k+y_k\le u_n+v_n\) . Thus \(u_n+v_n\) is an upper bound of the set \(\{x_k+y_k:k\ge n\}\) , and therefore \(w_n\le u_n+v_n\) for every \(n\) .

    The three sequences \((w_n)\) , \((u_n)\) , \((v_n)\) converge, to \(\limsup(x_n+y_n)\) , \(\limsup x_n\) , and \(\limsup y_n\) respectively. By the sum law and the order theorem (Theorems 2.4 and 2.5),

    \[ \limsup_{n\to\infty}(x_n+y_n)=\lim w_n\le\lim(u_n+v_n)=\limsup_{n\to\infty}x_n+\limsup_{n\to\infty}y_n . \]

    For strict inequality take \(x_n=(-1)^n\) and \(y_n=(-1)^{n+1}\) . Then \(x_n+y_n=0\) for all \(n\) , so the left side is \(0\) , while each limit superior on the right is \(1\) and the right side is \(2\) . The two sequences are large at different indices, which is the sequential version of Example 1.5.

19. Let \(S\) be a nonempty set of real numbers that is bounded above, and let \(s=\sup S\) . Prove that there is a sequence of elements of \(S\) converging to \(s\) , and that if \(s\notin S\) the sequence can be chosen strictly increasing.

    Solution

    Existence. For each \(n\in\mathbb N\) , Lemma 1.6 with \(\varepsilon=1/n\) gives an element \(x_n\in S\) with \(s-1/n<x_n\) ; also \(x_n\le s\) because \(s\) is an upper bound. Since \(s-1/n\to s\) , the squeeze theorem gives \(x_n\to s\) .

    Strictly increasing when \(s\notin S\) . Now every element of \(S\) is strictly less than \(s\) . Choose any \(x_1\in S\) . Suppose \(x_n\in S\) has been chosen; then \(x_n<s\) , so

    \[ \varepsilon_n=\min\{1/(n+1),\ s-x_n\} \]

    is positive. By Lemma 1.6 there is \(x_{n+1}\in S\) with \(x_{n+1}>s-\varepsilon_n\) . Then \(x_{n+1}>s-(s-x_n)=x_n\) , so the sequence is strictly increasing, and \(s-1/(n+1)<x_{n+1}<s\) , so it converges to \(s\) by the squeeze theorem.

    If \(s\in S\) and \(s\) is isolated from the rest of \(S\) , as for \(S=\{0,1\}\) , no strictly increasing sequence in \(S\) converges to \(s\) ; that is why the hypothesis \(s\notin S\) is needed for the second claim.

20. Find the flaw: “If \(\lvert x_{n+1}-x_n\rvert<1/n\) for all \(n\) , the differences tend to \(0\) , so the sequence is Cauchy.” Then prove that the stronger hypothesis \(\lvert x_{n+1}-x_n\rvert\le 2^{-n}\) does imply that \((x_n)\) is Cauchy.

    Hint

    The flaw is the step from “consecutive differences tend to \(0\) ” to “Cauchy”; the partial sums \(s_n\) of Exercise 13 satisfy \(\lvert s_{n+1}-s_n\rvert=1/(n+1)<1/n\) and are not Cauchy. Under the stronger hypothesis, for \(m>n\) estimate \(\lvert x_m-x_n\rvert\le\sum_{j=n}^{m-1}2^{-j}<2^{-n+1}\) , as in the proof of Proposition 2.17.

21. Let \(x_n\to L\) and let \(a_n=(x_1+\cdots+x_n)/n\) be the sequence of averages. Prove that \(a_n\to L\) , and show that the averages of the divergent sequence \(x_n=(-1)^n\) converge.

    Hint

    Replace \(x_n\) by \(x_n-L\) to reduce to \(L=0\) . Given \(\varepsilon>0\) choose \(N\) with \(\lvert x_n\rvert<\varepsilon/2\) for \(n>N\) . For \(n>N\) split the average: \(\lvert a_n\rvert\le(\lvert x_1\rvert+\cdots+\lvert x_N\rvert)/n+\varepsilon/2\) . The first term has a fixed numerator, so it is below \(\varepsilon/2\) for large \(n\) . For \(x_n=(-1)^n\) the averages are \(-1/n\) for odd \(n\) and \(0\) for even \(n\) .