§10 Monotone Sequences and Cauchy Sequences

This section gives two theorems, 10.2 and 10.11, that let us conclude a sequence converges without knowing the limit in advance. That matters, because in practice limits usually are not known in advance.

Monotone sequences

10.1 Definition.

A sequence $(s_n)$ is increasing if $s_n \le s_{n+1}$ for all $n$, and decreasing if $s_n \ge s_{n+1}$ for all $n$. If $(s_n)$ is increasing then $s_n \le s_m$ whenever $n < m$. A sequence that is increasing or decreasing is monotone (or monotonic).

(In the first edition of the book these were called “nondecreasing” and “nonincreasing”.)

Example 1.

$a_n = 1 - \frac1n$, $b_n = n^3$ and $c_n = \left(1 + \frac1n\right)^n$ are increasing, although this is not obvious for $(c_n)$. $d_n = \frac1{n^2}$ is decreasing. $s_n = (-1)^n$, $t_n = \cos\frac{n\pi}3$, $u_n = (-1)^n n$ and $v_n = \frac{(-1)^n}{n}$ are not monotonic, and neither is $x_n = n^{1/n}$ (look at its first four values in §7). Of these, $(a_n), (c_n), (d_n), (s_n), (t_n), (v_n), (x_n)$ are bounded, and $(b_n), (u_n)$ are unbounded.

10.2 Theorem.

All bounded monotone sequences converge.

Used in Remark 10.3, Exercise 10.2, Exercise 10.4, Theorem 11.5, §14, §15, Exercise 16.9, §18

Proof

Let $(s_n)$ be bounded and increasing, let $S = \{s_n : n \in \mathbb{N}\}$, and let $u = \sup S$, a real number. We show $\lim s_n = u$. Let $\varepsilon > 0$. Since $u - \varepsilon$ is not an upper bound for $S$, there is $N$ with $s_N > u - \varepsilon$. Since the sequence increases, $s_N \le s_n$ for $n \ge N$, and $s_n \le u$ always. So $n > N$ implies $u - \varepsilon < s_n \le u$, hence $|s_n - u| < \varepsilon$. The decreasing case is Exercise 10.2.

∎

The Completeness Axiom 4.4 is a vital ingredient here.

Try it: build a bounded increasing sequence

Choose a bound $M$ and build an increasing sequence that stays below it, by typing terms or using a rule. Whatever you do, the terms pile up below $M$ and creep toward their supremum, as Theorem 10.2 says. Try the rule “add $1/n$” to see why the bound is needed.

Upper bound M3First term s₁1Next term s_2Add term

+1 term+10 termsRun to 60Start over

bound M = 3 (dashed)latest term s_1level of the latest term

So far: n = 1, s_1 = 1.0000. Room left below M: 2.0000. The sup of these terms is just s_1, but the sequence may keep climbing.

Rule “close half of the gap to M” from s₁ = 1: the terms converge to sup sₙ ≈ 3.0000, which is the bound M itself (Theorem 10.2). Each step covers half of what is left, so s_n = M − (M − s₁)/2ⁿ⁻¹ and the sup is exactly M.

Type a value and press Enter to add it by hand. Every new term must be at least the last one and at most M.

Intuition

An increasing sequence that is bounded above has nowhere to go but up, and it cannot pass its supremum, so it creeps up toward it. Completeness is exactly what guarantees the supremum is there to creep toward. Over $\mathbb{Q}$ the theorem fails: the truncations $1, 1.4, 1.41, 1.414, \dots$ of $\sqrt2$ are rational, increasing and bounded, but have no rational limit. Theorem 10.2 is the Completeness Axiom restated for sequences.

Example 2.

Define $(s_n)$ recursively by

$$s_1 = 5 \qquad\text{and}\qquad s_n = \frac{s_{n-1}^2 + 5}{2s_{n-1}} \quad\text{for } n \ge 2. \tag{1}$$

So $s_2 = 3$ and $s_3 = \frac73 \approx 2.333$. An easy induction shows $s_n > 0$ for all $n$. We prove by induction that

$$\sqrt5 < s_{n+1} < s_n \le 5 \qquad\text{for } n \ge 1. \tag{2}$$

Since $\sqrt5 \approx 2.236$, (2) holds for $n \le 2$. Assume (2) holds for some $n$. To get $s_{n+2} < s_{n+1}$ we need $\frac{s_{n+1}^2 + 5}{2s_{n+1}} < s_{n+1}$, i.e. $5 < s_{n+1}^2$, which holds because $s_{n+1} > \sqrt5$. To get $s_{n+2} > \sqrt5$ we need $s_{n+1}^2 + 5 > 2\sqrt5\, s_{n+1}$, i.e. $(s_{n+1} - \sqrt5)^2 > 0$, which is true. So (2) holds for all $n$, and $s = \lim s_n$ exists by Theorem 10.2.

Since $s_4 = \frac{47}{21} \approx 2.238095$ and $\sqrt5 \approx 2.236068$, we suspect $s = \sqrt5$. Applying the limit theorems and $\lim s_{n+1} = s$ to $2 s_{n+1} s_n = s_n^2 + 5$ gives $2s^2 = s^2 + 5$. So $s^2 = 5$, and $s = \sqrt5$ since the limit is certainly not $-\sqrt5$.

Common pitfallprove the limit exists before you solve for it

The last step of Example 2, letting $n \to \infty$ in the recursion, is valid only because Theorem 10.2 already showed that the limit exists. Without that, the method gives nonsense. Take $s_1 = 1$ and $s_{n+1} = 2s_n$. “If $s = \lim s_n$, then $s = 2s$, so $s = 0$.” But $s_n = 2^{n-1} \to +\infty$. The equation only tells you what the limit must be if there is one.

Intuition

The recursion in Example 2 is Newton’s method for solving $x^2 = 5$ (see Remark 2.4 and §31): $s_n$ is where the tangent line to $y = x^2 - 5$ at $s_{n-1}$ crosses the axis. That is why it homes in on $\sqrt5$ so quickly.

10.3 Discussion of Decimals.

We restrict attention to nonnegative numbers. A decimal expansion $K.d_1d_2d_3d_4\cdots$, with $K$ a nonnegative integer and each $d_j \in \{0, 1, \dots, 9\}$, is shorthand for the limit of

$$s_n = K + \frac{d_1}{10} + \frac{d_2}{10^2} + \cdots + \frac{d_n}{10^n}. \tag{1}$$

$(s_n)$ is increasing and bounded (by $K + 1$; Exercise 10.3), so it converges by Theorem 10.2. Borrowing the geometric series formula from §14,

$$\lim_{n\to\infty} a(1 + r + r^2 + \cdots + r^n) = \frac{a}{1-r} \quad\text{for } |r| < 1, \tag{2}$$

we see $3.3333\cdots$ represents $\frac{3}{1 - \frac1{10}} = \frac{10}3$, and $0.9999\cdots$ represents $\frac{9/10}{1 - 1/10} = 1$. So $0.9999\cdots$ and $1.0000\cdots$ are different decimal expansions of the same real number. Conversely, every nonnegative real number has at least one decimal expansion; see §16.

Unbounded monotone sequences also have limits.

10.4 Theorem.

1. If $(s_n)$ is an unbounded increasing sequence, then $\lim s_n = +\infty$.
2. If $(s_n)$ is an unbounded decreasing sequence, then $\lim s_n = -\infty$.

Used in Exercise 10.5, §14

Proof

(i) Let $M > 0$. The set $\{s_n\}$ is bounded below by $s_1$, so it must be unbounded above, and $s_N > M$ for some $N$. Then $n > N$ implies $s_n \ge s_N > M$. (ii) is Exercise 10.5.

∎

10.5 Corollary.

If $(s_n)$ is monotone, then it either converges, diverges to $+\infty$, or diverges to $-\infty$. Thus $\lim s_n$ is always meaningful for monotone sequences.

Used in §5

lim sup and lim inf

The limiting behavior of a bounded sequence $(s_n)$ depends only on the tails $\{s_n : n > N\}$. If $\lim s_n$ exists, it lies in $[u_N, v_N]$ for every $N$ (Exercise 8.9), where

$$u_N = \inf\{s_n : n > N\} \qquad\text{and}\qquad v_N = \sup\{s_n : n > N\}.$$

As $N$ increases the tails shrink, so $u_1 \le u_2 \le u_3 \le \cdots$ and $v_1 \ge v_2 \ge v_3 \ge \cdots$ (Exercise 4.7(a)). By Theorem 10.2, $u = \lim u_N$ and $v = \lim v_N$ exist, and $u \le v$. These numbers are useful whether or not $\lim s_n$ exists.

10.6 Definition.

Let $(s_n)$ be a sequence in $\mathbb{R}$. Define

$$\limsup s_n = \lim_{N\to\infty} \sup\{s_n : n > N\} \tag{1}$$$$\liminf s_n = \lim_{N\to\infty} \inf\{s_n : n > N\}. \tag{2}$$

If $(s_n)$ is not bounded above, $\sup\{s_n : n > N\} = +\infty$ for all $N$ and we decree $\limsup s_n = +\infty$. Likewise $\liminf s_n = -\infty$ if $(s_n)$ is not bounded below.

Used in Exercise 11.8, §12, Exercise 12.1, §14, Theorem 14.9

$\limsup s_n$ need not equal $\sup\{s_n\}$, but $\limsup s_n \le \sup\{s_n : n \in \mathbb{N}\}$. Some terms may be much larger than $\limsup s_n$. Roughly, $\limsup s_n$ is the largest value that infinitely many terms get close to. This is made precise in Theorem 11.8 and §12.

Intuition

Think of $v_N$ as the ceiling over the tail that starts after $N$, and $u_N$ as its floor. Throwing away early terms can only lower the ceiling and raise the floor. $\limsup s_n$ and $\liminf s_n$ are where the ceiling and floor finally settle, and they ignore any finite number of unusual early terms.

Try it: watch the tails

The blue curve is $v_N$ and the orange curve is $u_N$, plotted against $N$. They squeeze together exactly when the sequence has a limit (Theorem 10.7).

Terms shown60

sₙv_N = sup{sₙ : n > N}u_N = inf{sₙ : n > N}

lim sup = 1 and lim inf = −1, so the sequence diverges (Theorem 10.7). The even terms converge to 1 and the odd terms to −1.

At N = 60: v_N ≈ 1.0161 and u_N ≈ -1.0164. As N grows, v_N decreases toward lim sup sₙ and u_N increases toward lim inf sₙ.

10.7 Theorem.

Let $(s_n)$ be a sequence in $\mathbb{R}$.

1. If $\lim s_n$ is defined (as a real number, $+\infty$ or $-\infty$), then $\liminf s_n = \lim s_n = \limsup s_n$.
2. If $\liminf s_n = \limsup s_n$, then $\lim s_n$ is defined and $\lim s_n = \liminf s_n = \limsup s_n$.

Used in Theorem 10.11, Theorem 11.8, Corollary 12.3, Exercise 12.2, Exercise 12.12, §14

Proof

Write $u_N, v_N$ as above, $u = \lim u_N = \liminf s_n$ and $v = \lim v_N = \limsup s_n$.

(i) Suppose $\lim s_n = +\infty$ and let $M > 0$. There is $N$ with $s_n > M$ for $n > N$, so $u_N \ge M$, and $u_m \ge M$ for $m > N$. Thus $\lim u_N = +\infty$, i.e. $\liminf s_n = +\infty$, and likewise $\limsup s_n = +\infty$. The case $-\infty$ is similar.

Now suppose $\lim s_n = s \in \mathbb{R}$. Let $\varepsilon > 0$ and choose $N$ with $|s_n - s| < \varepsilon$ for $n > N$. Then $s_n < s + \varepsilon$ for $n > N$, so $v_m \le s + \varepsilon$ for $m > N$, hence $\limsup s_n \le s + \varepsilon$. This holds for every $\varepsilon > 0$, so $\limsup s_n \le s$. Similarly $s \le \liminf s_n$. Since $\liminf s_n \le \limsup s_n$, all three are equal.

(ii) The cases $\liminf s_n = \limsup s_n = \pm\infty$ are easy and left to the reader. Suppose $\liminf s_n = \limsup s_n = s \in \mathbb{R}$ and let $\varepsilon > 0$. Since $s = \lim v_N$, there is $N_0$ with $|s - \sup\{s_n : n > N_0\}| < \varepsilon$, so

$$s_n < s + \varepsilon \quad\text{for all } n > N_0. \tag{1}$$

Similarly there is $N_1$ with $\inf\{s_n : n > N_1\} > s - \varepsilon$, so

$$s_n > s - \varepsilon \quad\text{for all } n > N_1. \tag{2}$$

By (1) and (2), $|s_n - s| < \varepsilon$ for $n > \max\{N_0, N_1\}$.

∎

Cauchy sequences

If $(s_n)$ converges, then for large $N$ the numbers $v_N$ and $u_N$ are close, so all terms of the tail $\{s_n : n > N\}$ are close to each other. This leads to a concept of great theoretical importance.

10.8 Definition.

A sequence $(s_n)$ of real numbers is a Cauchy sequence if

$$\text{for each } \varepsilon > 0 \text{ there exists a number } N \text{ such that } m, n > N \text{ implies } |s_n - s_m| < \varepsilon. \tag{1}$$

Compare this with Definition 7.1: no limit $s$ appears.

Intuition

A Cauchy sequence is one whose terms eventually agree with each other to within any tolerance. You can check this using the terms alone, which is exactly what you need when the limit is unknown. Over $\mathbb{Q}$, Cauchy sequences need not converge: the truncations of $\sqrt2$ form a Cauchy sequence of rationals with no rational limit. So Theorem 10.11 below is one more way of saying that $\mathbb{R}$ has no gaps.

10.9 Lemma.

Convergent sequences are Cauchy sequences.

Used in Theorem 10.11

Proof

Suppose $\lim s_n = s$ and let $\varepsilon > 0$. Choose $N$ with $|s_n - s| < \frac\varepsilon2$ for $n > N$. Then for $m, n > N$,

$$|s_n - s_m| \le |s_n - s| + |s - s_m| < \frac\varepsilon2 + \frac\varepsilon2 = \varepsilon.$$∎

10.10 Lemma.

Cauchy sequences are bounded.

Used in Theorem 10.11

Proof

As in Theorem 9.1: with $\varepsilon = 1$ there is $N$ with $|s_n - s_m| < 1$ for $m, n > N$. In particular $|s_n| < |s_{N+1}| + 1$ for $n > N$, so $M = \max\{|s_{N+1}| + 1, |s_1|, \dots, |s_N|\}$ bounds the sequence.

∎

The next theorem is very important: to show a sequence converges, it suffices to check that it is Cauchy, a property that does not involve the limit.

10.11 Theorem.

A sequence is a convergent sequence if and only if it is a Cauchy sequence.

Used in Exercise 10.4, §13, Theorem 13.4, §14

Proof

Lemma 10.9 is one direction. For the other, let $(s_n)$ be Cauchy. It is bounded by Lemma 10.10, so by Theorem 10.7 we only need

$$\liminf s_n = \limsup s_n. \tag{1}$$

Let $\varepsilon > 0$ and choose $N$ with $|s_n - s_m| < \varepsilon$ for $m, n > N$. Then $s_n < s_m + \varepsilon$ for all $m, n > N$, so $s_m + \varepsilon$ is an upper bound for $\{s_n : n > N\}$ and $v_N \le s_m + \varepsilon$ for $m > N$. So $v_N - \varepsilon$ is a lower bound for $\{s_m : m > N\}$, and $v_N - \varepsilon \le u_N$. Hence

$$\limsup s_n \le v_N \le u_N + \varepsilon \le \liminf s_n + \varepsilon.$$

As $\varepsilon > 0$ is arbitrary, $\limsup s_n \le \liminf s_n$. The opposite inequality always holds, which proves (1).

∎

The proof relies on Theorem 10.7, which relies implicitly on the Completeness Axiom: completeness makes $\sup\{s_n : n > N\}$ and $\inf\{s_n : n > N\}$ meaningful, and Theorem 10.2 (itself relying on completeness) makes their limits meaningful. Exercises on $\limsup$ and $\liminf$ appear in §§11 and 12.

Common pitfallconsecutive terms are not enough

$|s_{n+1} - s_n| \to 0$ does not make a sequence Cauchy. For $s_n = \sqrt n$,

$$\sqrt{n+1} - \sqrt n = \frac{1}{\sqrt{n+1} + \sqrt n} \to 0,$$

yet $\sqrt n \to +\infty$. The Cauchy condition controls $|s_n - s_m|$ for all pairs $m, n > N$, however far apart. Small steps can still add up to a long walk.

For $s_n = \sqrt n$, consecutive terms get arbitrarily close: $\sqrt{n+1} - \sqrt n = \dfrac{1}{\sqrt{n+1} + \sqrt n} \to 0$. Is $(s_n)$ a Cauchy sequence?

NoYes, since consecutive terms get close

Try it: how wide is the tail?

For $m, n > N$ the largest possible $|s_n - s_m|$ is $v_N - u_N$, the height of the band that holds the tail. So $(s_n)$ is Cauchy exactly when this height can be made smaller than any $\varepsilon$. Compare $\sqrt n$ and the partial sums of $\sum 1/k$: their neighbouring terms get close together, but their tails never get narrow.

ε0.100Your N

Find the smallest N

n ≤ N (ignored)range of the tail, from u_N to v_Nu_N + ε (dashed)the two terms farthest apart

✗ N = 5 fails: m = 6 and n = 7 give |sₘ − sₙ| = 0.310 ≥ ε. The smallest N that works is 19.

The neighbours s_6 and s_7 differ by 0.310. Converges to 0, so it is Cauchy (Lemma 10.9). The tail after N lies within about 2/N of itself.

Tail ranges are computed from the terms with n ≤ 100,000.

Reading alongside Abbott

Abbott’s Section 2.4 has the Monotone Convergence Theorem (Theorem 10.2 here), and Section 2.6 the Cauchy Criterion (Theorem 10.11). The routes differ. Abbott proves that Cauchy sequences converge using the Bolzano–Weierstrass theorem (§11): a Cauchy sequence is bounded, so it has a convergent subsequence, and its terms are dragged along to the same limit. Ross avoids subsequences by using $\limsup$ and $\liminf$ instead, which Abbott meets only in an exercise (Exercise 2.4.7). Abbott’s Section 2.6 also makes a point worth knowing: given the Archimedean property, the Completeness Axiom, the nested interval property (§4), Theorem 10.2, Bolzano–Weierstrass and the Cauchy criterion are all equivalent. Any one of them could serve as the axiom that says $\mathbb{R}$ has no gaps. Ross makes a similar remark after Definition 13.2.

Practice: put the proof in order

The proof of Theorem 10.2 guesses the limit first (the supremum) and then checks it. Put the checking in order.

Put the proof in order: Monotone Convergence Theorem (Theorem 10.2)

These are the steps of the proof, shuffled. Use the buttons to move each step into place, then check.

1. Let $(s_n)$ be increasing and bounded. (A decreasing sequence is handled by applying the argument to $(-s_n)$.) Put $S = \{s_n : n \in \mathbb{N}\}$.
2. The set $S$ is nonempty and bounded above, so $u = \sup S$ exists by the Completeness Axiom.
3. Fix $\varepsilon > 0$. Since $u - \varepsilon$ is not an upper bound of $S$, some term satisfies $s_N > u - \varepsilon$.
4. For every $n > N$, monotonicity gives $s_n \ge s_N > u - \varepsilon$.
5. Also $s_n \le u$ for every $n$, because $u$ is an upper bound of $S$.
6. Hence $|s_n - u| < \varepsilon$ for all $n > N$, which says $s_n \to u$.

Practice: spot the error

Passing to the limit in a recursion is legitimate, but only once there is a limit to pass to.

Spot the error: a recursive sequence

One line of this argument is wrong. Press the button on the line you think is the mistake.

1. Let $s_1 = 1$ and $s_{n+1} = 2s_n + 1$. We find $\lim s_n$.
2. Let $s = \lim s_n$.
3. Then also $s_{n+1} \to s$, so letting $n \to \infty$ in the recursion gives $s = 2s + 1$.
4. Therefore $s = -1$.

Check your understanding

Take the quiz (3 questions)

Which sequence converges by Theorem 10.2?

$s_n = 1 - \frac1n$$s_n = (-1)^n$$s_n = n$

Suppose $\lim (s_{n+1} - s_n) = 0$. Must $(s_n)$ be a Cauchy sequence?

Yes: consecutive terms get close, which is what Cauchy means.No: $s_n = \sqrt n$ has $s_{n+1} - s_n \to 0$ but is unbounded.

Let $s_n = (-1)^n \left(1 + \frac1n\right)$. What are $\limsup s_n$ and $\liminf s_n$?

$\limsup s_n = 1$ and $\liminf s_n = -1$$\limsup s_n = \frac32$ and $\liminf s_n = -2$Both are $0$.

Exercises

Exercise 10.1

Which of the following sequences are increasing? decreasing? bounded?

1. $\frac1n$
2. $\frac{(-1)^n}{n^2}$
3. $n^5$
4. $\sin\frac{n\pi}7$
5. $(-2)^n$
6. $\frac{n}{3^n}$

Solution

(a) decreasing, bounded (b) bounded, not monotone (c) increasing, unbounded (d) bounded, not monotone (e) neither monotone nor bounded (f) decreasing (since $\frac{n+1}{3^{n+1}} \le \frac{n}{3^n}$ iff $n + 1 \le 3n$), bounded

Tags: Warm-upComputation

Exercise 10.2

Prove Theorem 10.2 for bounded decreasing sequences.

Hint

Use $\inf\{s_n\}$, or apply the increasing case to $(-s_n)$.

Solution

Let $(s_n)$ be decreasing and bounded. Then $(-s_n)$ is increasing and bounded, so it converges by the increasing case of Theorem 10.2, say to $t$. By Theorem 9.2 (with $k = -1$), $s_n = -(-s_n) \to -t$, so $(s_n)$ converges (to $\inf\{s_n\}$).

Tags: StandardMonotone & Cauchy

Used in Theorem 10.2

Exercise 10.3

For a decimal expansion $K.d_1d_2d_3\cdots$ let $(s_n)$ be as in 10.3. Prove $s_n < K + 1$ for all $n$.

Hint

$\frac{9}{10} + \frac9{10^2} + \cdots + \frac9{10^n} = 1 - \frac1{10^n}$ for all $n$.

Solution

Here $s_n = K + \frac{d_1}{10} + \cdots + \frac{d_n}{10^n}$ with each digit $d_j \le 9$. Hence $s_n \le K + 9\left(\frac1{10} + \cdots + \frac1{10^n}\right) = K + \left(1 - \frac1{10^n}\right) < K + 1 .$

Tags: StandardMonotone & Cauchy

Used in Remark 10.3

Exercise 10.4

Discuss why Theorems 10.2 and 10.11 would fail if we restricted our world of numbers to the set $\mathbb{Q}$ of rational numbers.

Solution

The decimal truncations $1, 1.4, 1.41, 1.414, \dots$ of $\sqrt2$ form a bounded increasing sequence of rationals that is also Cauchy, but it has no rational limit.

Tags: Warm-upExplain why

Exercise 10.5

Prove Theorem 10.4(ii).

Solution

Let $(s_n)$ be an unbounded decreasing sequence. It is bounded above by $s_1$, so it must be unbounded below. Given $M$, there is $N$ with $s_N < M$, and then $n > N$ implies $s_n \le s_N < M$. Hence $\lim s_n = -\infty$.

(Alternatively, $(-s_n)$ is unbounded and increasing, so $-s_n \to +\infty$ by part (i), and Exercise 9.10(b) gives $s_n \to -\infty$.)

Tags: StandardMonotone & Cauchy

Used in Theorem 10.4

Exercise 10.6

1. Let $(s_n)$ be a sequence with $|s_{n+1} - s_n| < 2^{-n}$ for all $n$. Prove $(s_n)$ is a Cauchy sequence and hence convergent.
2. Is the result in (a) true if we only assume $|s_{n+1} - s_n| < \frac1n$ for all $n$?

Solution

(a) For $m > n$, $|s_m - s_n| \le \sum_{k=n}^{m-1} 2^{-k} < 2^{-n+1}$, which is small for large $n$. (b) No: $s_n = \frac12 + \frac13 + \cdots + \frac1n$ has $|s_{n+1} - s_n| = \frac1{n+1} < \frac1n$ but diverges to $+\infty$ (§14, §15).

Tags: StandardMonotone & Cauchy

Exercise 10.7

Let $S$ be a bounded nonempty subset of $\mathbb{R}$ such that $\sup S$ is not in $S$. Prove there is a sequence $(s_n)$ of points in $S$ with $\lim s_n = \sup S$. See also Exercise 11.11.

Hint

Pick $s_1 \in S$ with $s_1 > \sup S - 1$, then $s_{n+1} \in S$ with $s_{n+1} > \max\{s_n, \sup S - \frac1{n+1}\}$. This is possible because $s_n < \sup S$.

Solution

Let $s = \sup S \notin S$. Every element of $S$ is then strictly less than $s$. By the definition of supremum, pick $s_1 \in S$ with $s_1 > s - 1$. Having chosen $s_n \in S$, we have $s_n < s$ and $s - \frac1{n+1} < s$, so $\max\{s_n, s - \frac1{n+1}\} < s$, and there is $s_{n+1} \in S$ exceeding this maximum. The resulting sequence satisfies $s - \tfrac1n < s_n < s \quad \text{for all } n,$ so $s_n \to s$ by squeezing.

Tags: StandardSup & infSequences & continuity

Used in Exercise 11.11

Exercise 10.8

Let $(s_n)$ be an increasing sequence of positive numbers and define $\sigma_n = \frac1n(s_1 + s_2 + \cdots + s_n)$. Prove $(\sigma_n)$ is increasing.

Hint

$\sigma_{n+1} - \sigma_n = \frac{1}{n+1}\bigl(s_{n+1} - \sigma_n\bigr)$, and $\sigma_n \le s_n \le s_{n+1}$.

Solution

Since $\sigma_{n+1} = \dfrac{n\sigma_n + s_{n+1}}{n+1}$, $\sigma_{n+1} - \sigma_n = \frac{s_{n+1} - \sigma_n}{n+1}.$ Now $\sigma_n$ is the average of $s_1, \dots, s_n$, each at most $s_n$ because the sequence is increasing, so $\sigma_n \le s_n \le s_{n+1}$. Hence $\sigma_{n+1} - \sigma_n \ge 0$, and $(\sigma_n)$ is increasing.

Tags: StandardMonotone & CauchyInequalities

Exercise 10.9

Let $s_1 = 1$ and $s_{n+1} = \left(\frac{n}{n+1}\right) s_n^2$ for $n \ge 1$.

1. Find $s_2$, $s_3$ and $s_4$.
2. Show $\lim s_n$ exists.
3. Prove $\lim s_n = 0$.

Solution

(a) $\frac12, \frac16, \frac1{48}$. (b) By induction $0 < s_n \le 1$, so $s_{n+1} \le s_n^2 \le s_n$: decreasing and bounded below. (c) If $s = \lim s_n$, then $s = 1 \cdot s^2$, so $s \in \{0, 1\}$. Since $s \le s_2 = \frac12$, $s = 0$.

Tags: StandardMonotone & CauchyInduction

Exercise 10.10

Let $s_1 = 1$ and $s_{n+1} = \frac13(s_n + 1)$ for $n \ge 1$.

1. Find $s_2$, $s_3$ and $s_4$.
2. Use induction to show $s_n > \frac12$ for all $n$.
3. Show $(s_n)$ is a decreasing sequence.
4. Show $\lim s_n$ exists and find $\lim s_n$.

Solution

(a) $\frac23, \frac59, \frac{14}{27}$. (b) If $s_n > \frac12$ then $s_{n+1} > \frac13 \cdot \frac32 = \frac12$. (c) $s_{n+1} < s_n \iff s_n + 1 < 3s_n \iff s_n > \frac12$. (d) The limit $s$ satisfies $s = \frac13(s + 1)$, so $s = \frac12$.

Tags: StandardMonotone & CauchyInduction

Exercise 10.11

Let $t_1 = 1$ and $t_{n+1} = \left[1 - \frac1{4n^2}\right] t_n$ for $n \ge 1$.

1. Show $\lim t_n$ exists.
2. What do you think $\lim t_n$ is?

Solution

(a) $0 < t_{n+1} < t_n$, so the sequence decreases and is bounded below by $0$. (b) It is Wallis’s product: $\lim t_n = \frac2\pi \approx 0.6366$. Computing a few hundred terms suggests a number near $0.637$.

Tags: StandardMonotone & Cauchy

Exercise 10.12

Let $t_1 = 1$ and $t_{n+1} = \left[1 - \frac1{(n+1)^2}\right] t_n$ for $n \ge 1$.

1. Show $\lim t_n$ exists.
2. What do you think $\lim t_n$ is?
3. Use induction to show $t_n = \frac{n+1}{2n}$.
4. Repeat part (b).

Solution

(c) $\frac{n+1}{2n} \cdot \frac{(n+1)^2 - 1}{(n+1)^2} = \frac{n+1}{2n} \cdot \frac{n(n+2)}{(n+1)^2} = \frac{n+2}{2(n+1)}$. (d) $\lim t_n = \frac12$.

Tags: StandardMonotone & CauchyInduction