High School Mathematics · Grades 10–12

20Sequences

A sequence is a list of real numbers indexed by the natural numbers. Sequences model discrete evolutions — populations counted year by year, balances of a bank account, successive approximations of a number — and their limits are the first serious encounter with the infinite. This chapter sets up the vocabulary, the principle of induction, and the fundamental convergence theorems.

20.1 Reasoning by induction

Theorem 20.1 (Principle of induction)

Let $P(n)$ be a statement depending on an integer $n$ , and let $n_0 \in \N$ . If

(base case) $P(n_0)$ is true, and
(inductive step) for every $n \geq n_0$ , $P(n)$ implies $P(n+1)$ ,

then $P(n)$ is true for every $n \geq n_0$ .

Proof. Suppose, for contradiction, that the set $A$ of integers $n \geq n_0$ for which $P(n)$ is false is nonempty. Then $A$ has a smallest element $m$ .¹ Since $P(n_0)$ is true, $m > n_0$ , so $m - 1 \geq n_0$ and $m-1 \notin A$ , i.e. $P(m-1)$ is true. The inductive step applied to $n = m-1$ then shows that $P(m)$ is true, contradicting $m \in A$ . ∎

Example 20.2

Let us prove Bernoulli’s inequality: for every real $a > 0$ and every $n \in \N$ ,

(1+a)^n \geq 1 + na.

Base case. For $n = 0$ , both sides equal $1$ . Inductive step. Suppose $(1+a)^n \geq 1+na$ for some $n \in \N$ . Since $1 + a > 0$ , multiplying both sides by $1+a$ preserves the inequality:

(1+a)^{n+1} \geq (1+na)(1+a) = 1 + (n+1)a + na^2 \geq 1 + (n+1)a .

By induction, the inequality holds for all $n \in \N$ .

Method 20.3 (Writing an induction proof)

Always make the statement $P(n)$ explicit before starting. A complete proof has three visible parts: the base case, the inductive step (“assume $P(n)$ ; we prove $P(n+1)$ ”), and the conclusion invoking the principle of induction. The most common error is to prove the inductive step without ever using the hypothesis $P(n)$ : if that happens, either the proof is wrong or induction was not needed.

20.2 Vocabulary of sequences

Definition 20.4 (Sequence)

A sequence is a function $u \colon \N \to \R$ (or from $\{n \in \N : n \geq n_0\}$ to $\R$ ). The image of $n$ is written $u_n$ , and the sequence itself $(u_n)_{n\in\N}$ or simply $(u_n)$ .

A sequence may be defined explicitly, by a formula $u_n = f(n)$ , or by recurrence, by its first term and a relation $u_{n+1} = f(u_n)$ .

Definition 20.5 (Monotonicity)

A sequence $(u_n)$ is increasing if $u_{n+1} \geq u_n$ for all $n$ , decreasing if $u_{n+1} \leq u_n$ for all $n$ , and monotonic if it is increasing or decreasing. It is strictly increasing (resp. decreasing) when the inequalities are strict.

Method 20.6 (Studying the monotonicity of a sequence)

Three standard techniques:

study the sign of $u_{n+1} - u_n$ ;
if all terms are positive, compare $\dfrac{u_{n+1}}{u_n}$ to $1$ ;
if $u_n = f(n)$ with $f$ defined on $\intco{0}{+\infty}$ , use the variations of $f$ .

Definition 20.7 (Bounded sequence)

A sequence $(u_n)$ is bounded above if there exists $M \in \R$ with $u_n \leq M$ for all $n$ ; bounded below if there exists $m \in \R$ with $u_n \geq m$ for all $n$ ; and bounded if both hold.

20.2.1 Arithmetic and geometric sequences

Definition 20.8 (Arithmetic and geometric sequences)

A sequence $(u_n)$ is arithmetic with common difference $r$ if $u_{n+1} = u_n + r$ for all $n$ , and geometric with common ratio $q$ if $u_{n+1} = q\,u_n$ for all $n$ .

Proposition 20.9 (Explicit form and sums)

Let $n \in \N$ .

If $(u_n)$ is arithmetic with common difference $r$ , then $u_n = u_0 + nr$ and

$u_0 + u_1 + \dots + u_n = (n+1)\,\frac{u_0 + u_n}{2}.$
If $(u_n)$ is geometric with common ratio $q \neq 1$ , then $u_n = u_0\, q^n$ and

$u_0 + u_1 + \dots + u_n = u_0\,\frac{1 - q^{n+1}}{1 - q}.$

Proof. The explicit forms follow by immediate inductions. For the arithmetic sum, write $S = u_0 + \dots + u_n$ and add the same sum written in reverse order: each of the $n+1$ column sums equals $u_0 + u_n$ , so $2S = (n+1)(u_0+u_n)$ . For the geometric sum, compute $S - qS$ : all terms cancel in pairs except the first and the last, so $(1-q)S = u_0(1 - q^{n+1})$ . ∎

20.3 Limit of a sequence

Definition 20.10 (Convergent sequence)

A sequence $(u_n)$ converges to the real number $\ell$ if every open interval containing $\ell$ contains all the terms $u_n$ from some index on. We then write $\lim\limits_{n\to+\infty} u_n = \ell$ .

Equivalently: for every $\varepsilon > 0$ , there exists $N \in \N$ such that for all $n \geq N$ , $\abs{u_n - \ell} \leq \varepsilon$ .

Convergence of u_n = 2 + (-1)n/n to = 2: given > 0, all terms from the index N on lie in the band [ - , + ]. — Convergence of $u_n = 2 + \frac{(-1)^n}{n}$ to $\ell = 2$ : given $\varepsilon > 0$ , all terms from the index $N$ on lie in the band $\intcc{\ell-\varepsilon}{\ell+\varepsilon}$ .

Definition 20.11 (Divergence to infinity)

The sequence $(u_n)$ tends to $+\infty$ if for every $A \in \R$ , there exists $N \in \N$ such that $u_n \geq A$ for all $n \geq N$ . We write $\lim\limits_{n\to+\infty} u_n = +\infty$ ; the definition of $\lim u_n = -\infty$ is analogous. A sequence that does not converge is said to diverge.

Remark 20.12

A sequence can diverge without tending to $\pm\infty$ : the sequence $u_n = (-1)^n$ takes only the values $1$ and $-1$ and has no limit.

Proposition 20.13 (Uniqueness of the limit)

If $(u_n)$ converges, its limit is unique.

Proof. Suppose $u_n \to \ell$ and $u_n \to \ell'$ with $\ell \neq \ell'$ , say $\ell < \ell'$ . Set $\varepsilon = \frac{\ell' - \ell}{3} > 0$ . From some index on, $\abs{u_n - \ell} \leq \varepsilon$ and $\abs{u_n - \ell'} \leq \varepsilon$ , hence

\ell' - \ell \leq \abs{\ell' - u_n} + \abs{u_n - \ell} \leq 2\varepsilon = \tfrac{2}{3}(\ell' - \ell) < \ell' - \ell,

a contradiction. ∎

Proposition 20.14 (Operations on limits)

Let $(u_n)$ and $(v_n)$ be sequences with limits $\ell$ and $\ell'$ (finite or infinite). Then, whenever the right-hand side is not an indeterminate form,

\lim (u_n + v_n) = \ell + \ell', \qquad \lim (u_n v_n) = \ell\,\ell', \qquad \lim \frac{u_n}{v_n} = \frac{\ell}{\ell'}.

The indeterminate forms are $(+\infty) + (-\infty)$ , $0 \times \infty$ , $\frac{\infty}{\infty}$ and $\frac{0}{0}$ .

Proof. We prove the sum rule for finite limits; the other cases are similar and left as exercises. Let $\varepsilon > 0$ . There exist $N_1, N_2$ such that $\abs{u_n - \ell} \leq \varepsilon/2$ for $n \geq N_1$ and $\abs{v_n - \ell'} \leq \varepsilon/2$ for $n \geq N_2$ . For $n \geq \max(N_1, N_2)$ , the triangle inequality gives

\abs{(u_n + v_n) - (\ell + \ell')} \leq \abs{u_n - \ell} + \abs{v_n - \ell'} \leq \varepsilon. \qedhere

∎

Method 20.15 (Lifting an indeterminate form)

Faced with an indeterminate form, factor out the dominant term. For instance

n^2 - n = n^2\left(1 - \tfrac{1}{n}\right) \xrightarrow[n\to+\infty]{} +\infty, \qquad \frac{2n^2+1}{n^2 - n} = \frac{2 + 1/n^2}{1 - 1/n} \xrightarrow[n\to+\infty]{} 2 .

20.4 Convergence theorems

Theorem 20.16 (Comparison and squeeze theorems)

Let $(u_n)$ , $(v_n)$ , $(w_n)$ be sequences.

If $u_n \leq v_n$ from some index on and $u_n \to +\infty$ , then $v_n \to +\infty$ .
(Squeeze theorem) If $u_n \leq v_n \leq w_n$ from some index on and $(u_n)$ and $(w_n)$ both converge to the same limit $\ell$ , then $(v_n)$ converges to $\ell$ .

Proof. 1. Let $A \in \R$ . Since $u_n \to +\infty$ , there is $N$ with $u_n \geq A$ for $n \geq N$ ; enlarging $N$ if needed, $v_n \geq u_n \geq A$ for $n \geq N$ .

2. Let $\varepsilon > 0$ . From some index on, both $\ell - \varepsilon \leq u_n$ and $w_n \leq \ell + \varepsilon$ hold, hence $\ell - \varepsilon \leq u_n \leq v_n \leq w_n \leq \ell + \varepsilon$ , that is $\abs{v_n - \ell} \leq \varepsilon$ . ∎

Example 20.17

For all $n \geq 1$ , $-\frac{1}{n} \leq \frac{(-1)^n}{n} \leq \frac{1}{n}$ , and both bounds tend to $0$ ; hence $\frac{(-1)^n}{n} \to 0$ .

Theorem 20.18 (Monotone convergence theorem)

An increasing sequence that is bounded above converges. A decreasing sequence that is bounded below converges. An increasing sequence that is not bounded above tends to $+\infty$ .

Partial proof. We prove the third statement. Let $(u_n)$ be increasing and not bounded above, and let $A \in \R$ . Since $A$ is not an upper bound, there exists $N$ with $u_N \geq A$ ; by monotonicity, $u_n \geq u_N \geq A$ for all $n \geq N$ . Hence $u_n \to +\infty$ .

The two convergence statements rely on the least upper bound property of $\R$ ; they are admitted at this level (and proved in the first year of university). ∎

Remark 20.19

The theorem guarantees the existence of the limit but does not give its value. An increasing sequence bounded above by $M$ converges to some $\ell \leq M$ , not necessarily to $M$ .

Theorem 20.20 (Limit of geometric sequences)

Let $q \in \R$ .

If $q > 1$ , then $q^n \to +\infty$ .
If $q = 1$ , then $q^n \to 1$ .
If $\abs{q} < 1$ , then $q^n \to 0$ .
If $q \leq -1$ , then $(q^n)$ diverges and has no limit.

Proof. 1. Write $q = 1 + a$ with $a > 0$ . Bernoulli’s inequality (Example 20.2) gives $q^n \geq 1 + na \to +\infty$ , and we conclude by comparison (Theorem 20.16).

2. Immediate.

3. If $q = 0$ the claim is clear. Otherwise $\abs{q} < 1$ gives $1/\abs{q} > 1$ , so $(1/\abs{q})^n \to +\infty$ by point 1, hence $\abs{q}^n \to 0$ , and $-\abs{q}^n \leq q^n \leq \abs{q}^n$ allows us to conclude by the squeeze theorem.

4. For $q \leq -1$ , $(q^{2n})$ takes values $\geq 1$ while $(q^{2n+1})$ takes values $\leq -1$ : no single limit can attract both subsequences. ∎

The three behaviours of (qn): divergence to +∈fty for q > 1 (red), convergence to 0 for q < 1 (blue), and damped oscillation — still convergence to 0 — for -1 < q < 0 (orange). — The three behaviours of $(q^n)$ : divergence to $+\infty$ for $q > 1$ (red), convergence to $0$ for $\abs q < 1$ (blue), and damped oscillation — still convergence to $0$ — for $-1 < q < 0$ (orange).

Method 20.21 (Recurrent sequences $u_{n+1} = f(u_n)$ )

To study a sequence defined by $u_{n+1} = f(u_n)$ :

prove by induction that $(u_n)$ stays in an interval $I$ on which $f$ is well behaved (and, often, that $(u_n)$ is monotonic);
deduce convergence from the monotone convergence theorem;
pass to the limit in the relation $u_{n+1} = f(u_n)$ : if $f$ is continuous and $u_n \to \ell \in I$ , then $\ell$ satisfies $f(\ell) = \ell$ (see Chapter 21); solve this equation and select the right root.

Staircase construction for u_n+1 = √u_n + 2, u_0 = 0 (): each vertical step reads f(u_n) on the curve, each horizontal step carries it back through y = x. The sequence climbs to the fixed point = 2, where the curve meets the line. — Staircase construction for $u_{n+1} = \sqrt{u_n + 2}$ , $u_0 = 0$ (Exercise 20.6): each vertical step reads $f(u_n)$ on the curve, each horizontal step carries it back through $y = x$ . The sequence climbs to the fixed point $\ell = 2$ , where the curve meets the line.

Example 20.22

Let $u_0 = 2$ and $u_{n+1} = \frac{1}{2}\left(u_n + \frac{2}{u_n}\right)$ . One checks by induction that $u_n \geq \sqrt{2}$ for all $n$ (the inequality $\frac{1}{2}(x + 2/x) \geq \sqrt{2}$ for $x>0$ is equivalent to $(x - \sqrt2)^2 \geq 0$ ), then that $(u_n)$ is decreasing, since

u_{n+1}-u_n=\frac{2-u_n^2}{2u_n}\leq 0 .

Decreasing and bounded below, $(u_n)$ converges to some $\ell \geq \sqrt{2}$ , which must satisfy $\ell = \frac{1}{2}(\ell + 2/\ell)$ , i.e. $\ell^2 = 2$ . Hence $u_n \to \sqrt{2}$ . This is Heron’s algorithm, already used by the Babylonians; its convergence is extremely fast ( $u_3$ already gives $\sqrt 2$ to eight decimal places).

20.5 Exercises

Exercise 20.1 ★

Prove by induction that for all $n \in \N$ ,

1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}.

Solution

Solution of Exercise 20.1.

Let $P(n)$ be the statement $\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$ . Base case: for $n = 0$ both sides are $0$ (empty sum). Inductive step: assume $P(n)$ . Then

\sum_{k=1}^{n+1} k^2 = \frac{n(n+1)(2n+1)}{6} + (n+1)^2 = \frac{(n+1)\bigl(n(2n+1) + 6(n+1)\bigr)}{6} = \frac{(n+1)(2n^2 + 7n + 6)}{6}.

Since $2n^2 + 7n + 6 = (n+2)(2n+3)$ , this is $\frac{(n+1)(n+2)(2(n+1)+1)}{6}$ , which is $P(n+1)$ . By induction, $P(n)$ holds for all $n$ .

Exercise 20.2 ★

Study the monotonicity of the sequences defined for $n \geq 1$ by

a_n = \frac{n+1}{n}, \qquad b_n = \frac{2^n}{n}, \qquad c_n = n^2 - 10n .

Solution

Solution of Exercise 20.2.

$a_{n+1} - a_n = \frac{n+2}{n+1} - \frac{n+1}{n} = \frac{n(n+2) - (n+1)^2}{n(n+1)} = \frac{-1}{n(n+1)} < 0$ : $(a_n)$ is strictly decreasing.

$(b_n)$ has positive terms and $\frac{b_{n+1}}{b_n} = \frac{2^{n+1}}{n+1}\cdot\frac{n}{2^n} = \frac{2n}{n+1} \geq 1 \iff 2n \geq n+1 \iff n \geq 1$ : $(b_n)$ is increasing (strictly for $n \geq 2$ ).

$c_{n+1} - c_n = (n+1)^2 - 10(n+1) - n^2 + 10n = 2n - 9$ , which is negative for $n \leq 4$ and positive for $n \geq 5$ : $(c_n)$ decreases up to $c_5 = -25$ , its minimum, then increases. It is not monotonic.

Exercise 20.3 ★

Compute the limits of the sequences with general terms

u_n = \frac{3n^2 - n + 1}{2n^2 + 5}, \qquad v_n = \sqrt{n+1} - \sqrt{n}, \qquad w_n = \frac{2^n - 3^n}{3^n + 1}.

Solution

Solution of Exercise 20.3.

Factor dominant terms:

u_n = \frac{n^2(3 - 1/n + 1/n^2)}{n^2(2 + 5/n^2)} \xrightarrow[n\to+\infty]{} \frac{3}{2}.

Multiply by the conjugate:

v_n = \frac{(n+1) - n}{\sqrt{n+1} + \sqrt{n}} = \frac{1}{\sqrt{n+1}+\sqrt{n}} \xrightarrow[n\to+\infty]{} 0.

Divide numerator and denominator by $3^n$ :

w_n = \frac{(2/3)^n - 1}{1 + (1/3)^n} \xrightarrow[n\to+\infty]{} \frac{0-1}{1+0} = -1,

using $\lim q^n = 0$ for $\abs{q} < 1$ .

Exercise 20.4 ★

Let $(u_n)$ be the arithmetic sequence with $u_0 = 5$ and common difference $r = 3$ , and $(v_n)$ the geometric sequence with $v_0 = 8$ and common ratio $q = \frac{1}{2}$ . Compute $u_n$ , $v_n$ , $\sum_{k=0}^{n} u_k$ and $\sum_{k=0}^{n} v_k$ , and the limits of all four expressions as $n \to +\infty$ .

Solution

Solution of Exercise 20.4.

$u_n = 5 + 3n \to +\infty$ and $v_n = 8 \cdot (1/2)^n = 2^{3-n} \to 0$ . The sums are

\sum_{k=0}^{n} u_k = (n+1)\,\frac{5 + (5+3n)}{2} = \frac{(n+1)(10+3n)}{2} \xrightarrow[n\to+\infty]{} +\infty,

\sum_{k=0}^{n} v_k = 8\,\frac{1 - (1/2)^{n+1}}{1 - 1/2} = 16\left(1 - \left(\tfrac{1}{2}\right)^{n+1}\right) \xrightarrow[n\to+\infty]{} 16 .

Exercise 20.5 ★★

Using the squeeze theorem, compute

\lim_{n\to+\infty} \frac{n + \cos n}{n + 1} \qquad\text{and}\qquad \lim_{n\to+\infty} \frac{n!}{n^n},

where $n! = 1 \times 2 \times \dots \times n$ . For the second limit, bound $\frac{n!}{n^n}$ by a term of a geometric sequence.

Solution

Solution of Exercise 20.5.

Since $-1 \leq \cos n \leq 1$ ,

\frac{n-1}{n+1} \leq \frac{n + \cos n}{n+1} \leq 1,

and $\frac{n-1}{n+1} \to 1$ , so the limit is $1$ by the squeeze theorem.

For the second limit, write

0 \leq \frac{n!}{n^n} = \frac{1}{n}\cdot\frac{2}{n}\cdots\frac{n}{n} \leq \frac{1}{n},

because every factor $\frac{k}{n}$ with $2 \leq k \leq n$ is at most $1$ . Since $\frac1n \to 0$ , the squeeze theorem gives $\frac{n!}{n^n} \to 0$ . (The suggested geometric bound also works: each factor with $k \leq n/2$ is at most $\frac12$ , giving the stronger bound $(1/2)^{\floor{n/2}}$ .)

Exercise 20.6 ★★

Let $u_0 = 0$ and $u_{n+1} = \sqrt{u_n + 2}$ for all $n \in \N$ .

Prove by induction that $0 \leq u_n \leq 2$ for all $n$ .
Show that $(u_n)$ is increasing.
Deduce that $(u_n)$ converges and determine its limit.

Solution

Solution of Exercise 20.6.

1. $u_0 = 0 \in \intcc{0}{2}$ . If $0 \leq u_n \leq 2$ , then $2 \leq u_n + 2 \leq 4$ , so $\sqrt{2} \leq u_{n+1} \leq 2$ ; in particular $0 \leq u_{n+1} \leq 2$ . By induction the property holds for all $n$ .

2. $u_{n+1} - u_n = \sqrt{u_n + 2} - u_n$ . For $x \in \intcc{0}{2}$ , $\sqrt{x+2} \geq x \iff x + 2 \geq x^2 \iff (2-x)(x+1) \geq 0$ , which is true. Hence $(u_n)$ is increasing.

3. Increasing and bounded above by $2$ , $(u_n)$ converges to some $\ell \in \intcc{0}{2}$ . Passing to the limit in $u_{n+1} = \sqrt{u_n + 2}$ (the map $x \mapsto \sqrt{x+2}$ is continuous) gives $\ell = \sqrt{\ell + 2}$ , so $\ell^2 - \ell - 2 = 0$ , i.e. $\ell \in \{-1, 2\}$ . Since $\ell \geq 0$ , $\lim u_n = 2$ .

Exercise 20.7 ★★

A patient takes a dose of $1$ unit of a drug every morning. During each 24-hour period, the body eliminates $40\%$ of the drug present. Let $u_n$ be the quantity of drug in the body just after the dose on day $n$ , so that $u_0 = 1$ .

Justify that $u_{n+1} = 0.6\,u_n + 1$ .
Let $v_n = u_n - 2.5$ . Show that $(v_n)$ is geometric and deduce an explicit formula for $u_n$ .
Determine the long-term quantity of drug in the body.

Solution

Solution of Exercise 20.7.

1. Between two doses, $40\%$ of the drug is eliminated, so the quantity $u_n$ becomes $0.6\,u_n$ ; the next dose adds $1$ unit: $u_{n+1} = 0.6\,u_n + 1$ .

2. $v_{n+1} = u_{n+1} - 2.5 = 0.6\,u_n + 1 - 2.5 = 0.6(u_n - 2.5) = 0.6\,v_n$ : $(v_n)$ is geometric with ratio $0.6$ and first term $v_0 = 1 - 2.5 = -1.5$ . Hence $v_n = -1.5 \times 0.6^n$ and

u_n = 2.5 - 1.5 \times 0.6^n .

3. Since $0.6^n \to 0$ , $u_n \to 2.5$ : the quantity of drug stabilizes at $2.5$ units.

Exercise 20.8 ★★

Let $(u_n)$ be defined by $u_0 = 3$ and $u_{n+1} = \frac{4u_n - 1}{u_n + 2}$ .

Show by induction that $u_n > 1$ for all $n \in \N$ .
Show that $v_n = \dfrac{1}{u_n - 1}$ defines an arithmetic sequence.
Deduce explicit formulas for $v_n$ and $u_n$ , and the limit of $(u_n)$ .

Solution

Solution of Exercise 20.8.

1. $u_0 = 3 > 1$ . If $u_n > 1$ , then $u_n + 2 > 0$ and

u_{n+1} - 1 = \frac{4u_n - 1 - u_n - 2}{u_n + 2} = \frac{3(u_n - 1)}{u_n + 2} > 0 .

By induction, $u_n > 1$ for all $n$ (and in particular $u_n + 2 \neq 0$ , so the sequence is well defined).

2. Using the identity above,

v_{n+1} = \frac{1}{u_{n+1} - 1} = \frac{u_n + 2}{3(u_n - 1)} = \frac{(u_n - 1) + 3}{3(u_n - 1)} = \frac{1}{3} + v_n .

So $(v_n)$ is arithmetic with common difference $\frac13$ and $v_0 = \frac{1}{u_0 - 1} = \frac12$ .

3. $v_n = \frac12 + \frac{n}{3}$ , hence $u_n = 1 + \frac{1}{v_n} = 1 + \frac{6}{3 + 2n}$ . Since $v_n \to +\infty$ , $u_n \to 1$ .

Exercise 20.9 ★★★

For $n \geq 1$ , let $H_n = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ .

Show that for all $n \geq 1$ , $H_{2n} - H_n \geq \frac{1}{2}$ .
Deduce that $H_{2^k} \geq 1 + \frac{k}{2}$ for all $k \in \N$ , and conclude that $H_n \to +\infty$ .

Solution

Solution of Exercise 20.9.

1. $H_{2n} - H_n = \sum_{k=n+1}^{2n} \frac{1}{k}$ is a sum of $n$ terms, each at least $\frac{1}{2n}$ ; hence $H_{2n} - H_n \geq n \cdot \frac{1}{2n} = \frac12$ .

2. By induction on $k$ : $H_{2^0} = H_1 = 1 \geq 1$ . If $H_{2^k} \geq 1 + \frac{k}{2}$ , then applying point 1 with $n = 2^k$ ,

H_{2^{k+1}} \geq H_{2^k} + \frac12 \geq 1 + \frac{k+1}{2}.

The sequence $(H_n)$ is increasing (each step adds $\frac{1}{n+1} > 0$ ) and the subsequence $H_{2^k}$ is unbounded, so $(H_n)$ is not bounded above. Increasing and unbounded, it tends to $+\infty$ (Theorem 20.18).

Exercise 20.10 ★★★

(Adjacent sequences.) Two sequences $(a_n)$ and $(b_n)$ are adjacent if $(a_n)$ is increasing, $(b_n)$ is decreasing, and $b_n - a_n \to 0$ .

Show that for all $n$ , $a_n \leq b_n$ . (Hint: study the monotonicity of $(b_n - a_n)$ .)
Show that adjacent sequences both converge, to the same limit.
Application: show that the sequences $a_n = \sum_{k=0}^{n} \frac{1}{k!}$ and $b_n = a_n + \frac{1}{n \cdot n!}$ ( $n \geq 1$ ) are adjacent. (Their common limit is the number $\eu$ , studied in Chapter 23.)

Solution

Solution of Exercise 20.10.

1. The sequence $d_n = b_n - a_n$ satisfies $d_{n+1} - d_n = (b_{n+1} - b_n) - (a_{n+1} - a_n) \leq 0$ , so $(d_n)$ is decreasing; since $d_n \to 0$ , we get $d_n \geq 0$ for all $n$ (a decreasing sequence with a negative term would stay below it forever, preventing the limit $0$ ). Hence $a_n \leq b_n$ .

2. From $a_n \leq b_n \leq b_0$ , the increasing sequence $(a_n)$ is bounded above, so it converges to some $\ell$ . Similarly $(b_n)$ , decreasing and bounded below by $a_0$ , converges to some $\ell'$ . Then $\ell' - \ell = \lim (b_n - a_n) = 0$ , so $\ell = \ell'$ .

3. $(a_n)$ is (strictly) increasing since $a_{n+1} - a_n = \frac{1}{(n+1)!} > 0$ . For $(b_n)$ ,

b_{n+1} - b_n = \frac{1}{(n+1)!} + \frac{1}{(n+1)(n+1)!} - \frac{1}{n\,n!} = \frac{n(n+1) + n - (n+1)^2}{n(n+1)(n+1)!} = \frac{-1}{n(n+1)(n+1)!} < 0 ,

so $(b_n)$ is decreasing. Finally $b_n - a_n = \frac{1}{n\,n!} \to 0$ . The two sequences are adjacent, hence converge to a common limit.

20.6 Problem: Heron’s sequence, judged at last

Problem 20.1

Weekend problem — induction certifies, monotone convergence sentences, and the two-thousand-year-old recipe for $\sqrt2$ finally gets its proof (with Gauss’s marvellous mean for dessert)

Three times this series has met Heron’s recipe — average the guess with $2/\text{guess}$ — and three times it could only observe that the recipe works. This chapter at last owns the instruments of judgment: induction (Theorem 20.1), the monotone convergence theorem (Theorem 20.18), and limits of recurrences. The verdict, and the certified speed, occupy the heart of this problem; around it, induction’s classic traps, the slowest divergence in mathematics, and the fastest convergence Gauss ever found.

Part I — Induction warm-ups.

Prove by induction: $1 + 3 + 5 + \dots + (2n - 1) = n^2$ (the staircase of odd numbers, drawn in the Middle School volume, now certified).
Prove by induction that $2^n > n$ for every $n \in \N$ .
Prove Bernoulli’s inequality by induction: for $x \geq 0$ and $n \in \N$ , $(1 + x)^n \geq 1 + nx$ .
The classic trap: “all marbles have the same color — true for one marble; and if any $n$ marbles are always monochrome, then among $n + 1$ marbles the first $n$ share a color, the last $n$ share a color, so all $n + 1$ do.” Every child knows the conclusion is absurd: find the exact step where the induction breaks.
Prove by induction that $4^n - 1$ is divisible by $3$ for every $n \in \N$ .

Part II — The trial of Heron. Let $x_0 = 2$ and $x_{n+1} = \dfrac12\left(x_n + \dfrac{2}{x_n}\right)$ .

Compute $x_1$ , $x_2$ , $x_3$ as exact fractions (old friends).
Prove the key identity

$x_{n+1}^2 - 2 = \left(\frac{x_n^2 - 2}{2x_n}\right)^{\!2} \geq 0,$

and deduce by induction that $x_n > 0$ and $x_n^2 > 2$ for every $n$ .
Show that $(x_n)$ is strictly decreasing (compute $x_{n+1} - x_n$ and use question 7).
Invoke the monotone convergence theorem: why does $(x_n)$ converge to some limit $L \geq 1$ ?
Identify the limit: pass the recurrence to the limit (Proposition 20.14) and conclude $L = \sqrt2$ . State the historical verdict: after two thousand years of faithful service, Heron’s recipe is proved to converge.
The certified speed: with $e_n = x_n - \sqrt2$ , prove

$e_{n+1} = \frac{e_n^2}{2 x_n} ,$

and deduce $e_{n+1} \leq \frac{e_n^2}{2\sqrt2}$ : the error is squared at each step — the digit-doubling observed since the Middle School volume, now a theorem.
Confirm numerically: compute $e_0, e_1, e_2, e_3$ (from question 6) and check that each $\frac{e_{n+1}}{e_n^2}$ is close to $\frac{1}{2x_n}$ .

Part III — The slowest divergence.

Exercise 20.9 proved $H_{2^k} \geq 1 + \frac k2$ for the harmonic sums. How many terms guarantee $H_n > 10$ ? (A power of two will do; marvel at its size.)
By contrast, the geometric sums $1 + \frac12 + \frac14 + \dots + \frac{1}{2^n} = 2 - \frac{1}{2^n}$ converge to $2$ (Theorem 20.20): the chocolate-bar intuition of the Middle School volume, finally a limit statement. Write out the two-line proof.
Between the two: show that the sums $S_n = 1 + \frac{1}{4} + \frac{1}{9} + \dots + \frac{1}{n^2}$ converge, by bounding $\frac{1}{k^2} \leq \frac{1}{k(k-1)} = \frac{1}{k-1} - \frac{1}{k}$ (for $k \geq 2$ ), telescoping, and applying monotone convergence. (The limit, $\frac{\pi^2}{6}$ , is one of Euler’s miracles, proved in the university volumes.)
State the moral of questions 13–15 in two sentences: what does “the terms tend to $0$ ” decide about the convergence of the sums — and what does it not?

Part IV — Gauss’s arithmetic–geometric mean. Let $a_0 = 1$ , $b_0 = 2$ , and

a_{n+1} = \sqrt{a_n b_n}, \qquad b_{n+1} = \frac{a_n + b_n}{2} .

Compute $a_1, b_1, a_2, b_2$ (five decimals). What do you observe about the speed?
Show that $a_n \leq b_n$ for every $n$ (the arithmetic–geometric inequality, met throughout this series), that $(a_n)$ increases and $(b_n)$ decreases.
Show that $b_{n+1} - a_{n+1} \leq \frac{b_n - a_n}{2}$ (factor $b_{n+1} - a_{n+1} = \frac{(\sqrt{b_n} - \sqrt{a_n})^2}{2}$ and compare), and conclude with Exercise 20.10 that the two sequences are adjacent: they share a common limit $M(1, 2)$ , the arithmetic–geometric mean.
Compute $M(1, 2)$ to six decimals (how many iterations did you need?). On 30 May 1799, Gauss computed $M(1, \sqrt2)$ to eleven decimals, recognized $\frac{\pi}{M(1,\sqrt2)}$ as a known integral, and wrote that a “new field of analysis” had opened — it had: elliptic integrals, told in the university volumes. Close with the observed convergence speeds of this problem, slowest to fastest.

Solution

Solution of Problem 20.1.

1. True for $n = 1$ ( $1 = 1^2$ ). If $1 + 3 + \dots + (2n - 1) = n^2$ , then adding the next odd number: $n^2 + (2n + 1) = (n + 1)^2$ : heredity. By induction, true for all $n \geq 1$ .

2. $2^0 = 1 > 0$ . If $2^n > n$ , then $2^{n+1} = 2 \cdot 2^n > 2n \geq n + 1$ for $n \geq 1$ (and $n = 0$ checks directly): heredity, done.

3. $n = 0$ : $1 \geq 1$ . If $(1 + x)^n \geq 1 + nx$ , multiply by $1 + x \geq 1 > 0$ : $(1 + x)^{n+1} \geq (1 + nx)(1 + x) = 1 + (n + 1)x + nx^2 \geq 1 + (n + 1)x$ .

4. The step from $n = 1$ to $n = 2$ : among two marbles, “the first $n$ ” and “the last $n$ ” are two disjoint single marbles — no common marble bridges the two groups, so nothing forces their colors to agree. The heredity argument silently requires the two groups to overlap, true only from $n \geq 2$ ; with the base case $n = 1$ the chain never starts.

5. $4^0 - 1 = 0 = 3 \times 0$ . If $4^n - 1 = 3k$ , then $4^{n+1} - 1 = 4(4^n - 1) + 3 = 3(4k + 1)$ : heredity.

6. $x_1 = \frac32$ , $x_2 = \frac{17}{12}$ , $x_3 = \frac{577}{408}$ .

7. $x_{n+1}^2 - 2 = \frac{(x_n^2 + 2)^2 - 8x_n^2} {4x_n^2} = \frac{(x_n^2 - 2)^2}{4 x_n^2}$ : a square over a positive, hence $\geq 0$ , and $> 0$ whenever $x_n^2 \neq 2$ . Induction: $x_0 = 2 > 0$ with $x_0^2 = 4 > 2$ ; if $x_n > 0$ and $x_n^2 > 2$ , then $x_{n+1}$ (an average of positives) is positive and $x_{n+1}^2 - 2 > 0$ .

8. $x_{n+1} - x_n = \frac{2 - x_n^2}{2x_n} < 0$ by question 7: strictly decreasing.

9. Decreasing and bounded below (by $1$ , since $x_n^2 > 2 > 1$ and $x_n > 0$ ): by the monotone convergence theorem, $(x_n)$ converges to some $L \geq 1$ .

10. Limits respect the algebra: from $x_{n+1} = \frac12\left(x_n + \frac{2}{x_n}\right)$ and $x_n \to L \geq 1 > 0$ : $L = \frac12\left(L + \frac2L\right)$ , so $L^2 = 2$ and, $L$ being positive, $L = \sqrt2$ . Verdict: convergence proved, limit identified — Heron acquitted with honors.

11. $x_{n+1} - \sqrt2 = \frac{x_n^2 - 2\sqrt2\,x_n + 2}{2x_n} = \frac{(x_n - \sqrt2)^2}{2x_n}$ : exactly $e_{n+1} = \frac{e_n^2}{2x_n}$ , and $x_n > \sqrt2$ gives $e_{n+1} \leq \frac{e_n^2}{2\sqrt2}$ . Squared error: each step doubles the number of correct decimals, as observed since grade 9.

12. $e_0 \approx 0.5858$ , $e_1 \approx 0.0858$ , $e_2 \approx 0.00245$ , $e_3 \approx 2.1 \times 10^{-6}$ . Ratios $\frac{e_1}{e_0^2} \approx 0.25 = \frac{1}{2x_0}$ ; $\frac{e_2}{e_1^2} \approx 0.333 = \frac{1}{2x_1}$ ; $\frac{e_3}{e_2^2} \approx 0.353 \approx \frac{1}{2x_2}$ : the theorem in action.

13. $H_{2^{18}} \geq 1 + 9 = 10$ : about $260\,000$ terms ( $2^{18} = 262\,144$ ) merely to pass $10$ — divergence at a crawl (and $H_n > 100$ would need more terms than atoms in any library).

14. $S_n = 2 - \frac{1}{2^n}$ (geometric sum), and $\frac{1}{2^n} \to 0$ (Theorem 20.20), so $S_n \to 2$ : the endlessly bitten chocolate bar tends to, without ever reaching, the whole — now in the official language of limits.

15. For $k \geq 2$ : $\frac{1}{k^2} \leq \frac{1}{k(k-1)} = \frac{1}{k-1} - \frac1k$ , so $S_n \leq 1 + \left(1 - \frac1n\right) < 2$ : increasing and bounded above, hence convergent (monotone convergence). Euler later named the limit: $\frac{\pi^2}{6}$ .

16. Terms tending to $0$ is necessary for the sums to settle but decides nothing: the harmonic terms $\frac1n \to 0$ yet the sums blow up; the terms $\frac{1}{n^2} \to 0$ and the sums converge. How fast the terms die is the whole question — the theory of series, built in the university volumes.

17. $a_1 = \sqrt2 \approx 1.41421$ , $b_1 = 1.5$ ; $a_2 \approx 1.45648$ , $b_2 \approx 1.45711$ : two iterations already agree to three decimals — staggering speed.

18. $b_{n+1} - a_{n+1} = \frac{a_n + b_n}{2} - \sqrt{a_n b_n} = \frac{(\sqrt{b_n} - \sqrt{a_n})^2}{2} \geq 0$ : means stay ordered. $(a_n)$ increases: $a_{n+1} = \sqrt{a_n b_n} \geq \sqrt{a_n \cdot a_n} = a_n$ ; $(b_n)$ decreases symmetrically.

19. $\frac{b_{n+1} - a_{n+1}}{b_n - a_n} = \frac{(\sqrt{b_n} - \sqrt{a_n})^2} {2(\sqrt{b_n} - \sqrt{a_n})(\sqrt{b_n} + \sqrt{a_n})} = \frac{\sqrt{b_n} - \sqrt{a_n}}{2(\sqrt{b_n} + \sqrt{a_n})} \leq \frac12$ : the gap at least halves, so $b_n - a_n \to 0$ ; with question 18, the sequences are adjacent and share a limit $M(1, 2)$ .

20. Iteration three gives $a_3 \approx b_3 \approx 1.456791$ : $M(1, 2) \approx 1.456791$ in three turns of the crank (the gap roughly squares, like Heron’s). Speed ranking of the problem’s sequences, slowest to fastest: the harmonic sums (glacial divergence), the geometric sums (error halved each step), Heron and the AGM (error squared each step) — and it was the AGM’s unearthly speed that told Gauss he had struck a new vein of analysis.

Every nonempty subset of $\N$ has a smallest element; this property of $\N$ is taken as an axiom. ↩