---
title: "Sequences"
book: "High School Mathematics"
subject: math
language: en
chapter: 20
exercises: 10
source: https://one-course.com/books/math/2/en/chapter/20-sequences
---

# Chapter 20 — Sequences

A [sequence](#def-g12-seq-sequence) is a list of [real numbers](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) indexed by the [natural numbers](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets). [Sequences](#def-g12-seq-sequence) model discrete evolutions — populations counted year by year, balances of a bank account, successive [approximations](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-approx) 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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $n$, and let $n_0 \in \N$. If

1. *(base case)* $P(n_0)$ is true, and
2. *(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](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $n \geq n_0$ for which $P(n)$ is false is nonempty. Then $A$ has a smallest element $m$.[1](#fn-1) 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](https://one-course.com/books/math/2/en/chapter/11-functions-and-variations#def-g11-func-function) $u \colon \N \to \R$ (or from $\{n \in \N : n \geq n_0\}$ to $\R$). The [image](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-function) of $n$ is written $u_n$, and the sequence itself $(u_n)_{n\in\N}$ or simply $(u_n)$.

A [sequence](#def-g12-seq-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](#def-g12-seq-sequence) $(u_n)$ is *increasing* if $u_{n+1} \geq u_n$ for all $n$, *[decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations)* if $u_{n+1} \leq u_n$ for all $n$, and *monotonic* if it is increasing or [decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations). It is *strictly* increasing (resp. [decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations)) when the inequalities are strict.

**Method 20.6 (Studying the monotonicity of a sequence).**

Three standard techniques:

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

**Definition 20.7 (Bounded sequence).**

A [sequence](#def-g12-seq-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](#def-g12-seq-sequence) $(u_n)$ is *arithmetic* with [common difference](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#def-g11-seq-arithmetic) $r$ if $u_{n+1} = u_n + r$ for all $n$, and *geometric* with [common ratio](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#def-g11-seq-geometric) $q$ if $u_{n+1} = q\,u_n$ for all $n$.

**Proposition 20.9 (Explicit form and sums).**

Let $n \in \N$.

1. If $(u_n)$ is [arithmetic](#def-g12-seq-arith-geom) with [common difference](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#def-g11-seq-arithmetic) $r$, then $u_n = u_0 + nr$ and $$u_0 + u_1 + \dots + u_n = (n+1)\,\frac{u_0 + u_n}{2}.$$
2. If $(u_n)$ is [geometric](#def-g12-seq-arith-geom) with [common ratio](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#def-g11-seq-geometric) $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](#def-g12-seq-arith-geom) 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](#def-g12-seq-arith-geom) 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](#def-g12-seq-sequence) $(u_n)$ *converges* to the [real number](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-sets) $\ell$ if every open [interval](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-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 ( - , + ).](https://one-course.com/images/onecourse/chapters/math-2/g12-seq/fig-8991cce01fa0.svg)

*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](#def-g12-seq-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](#def-g12-seq-sequence) that does not converge is said to *diverge*.

**Remark 20.12.**

A [sequence](#def-g12-seq-sequence) can diverge without tending to $\pm\infty$: the [sequence](#def-g12-seq-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](#def-g12-seq-limit), 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](#def-g12-seq-sequence) 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](#def-g12-seq-sequence).

1. If $u_n \leq v_n$ from some index on and $u_n \to +\infty$ , then $v_n \to +\infty$ .
2. *(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](#def-g12-seq-limit) 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](#def-g12-seq-monotonic) [sequence](#def-g12-seq-sequence) that is [bounded above](#def-g12-seq-bounded) [converges](#def-g12-seq-limit). A [decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations) [sequence](#def-g12-seq-sequence) that is [bounded below](#def-g12-seq-bounded) [converges](#def-g12-seq-limit). An [increasing](#def-g12-seq-monotonic) [sequence](#def-g12-seq-sequence) that is not [bounded above](#def-g12-seq-bounded) tends to $+\infty$.

**Partial proof.** We prove the third statement. Let $(u_n)$ be [increasing](#def-g12-seq-monotonic) and not [bounded above](#def-g12-seq-bounded), 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](#def-g12-seq-monotonic) [sequence](#def-g12-seq-sequence) [bounded above](#def-g12-seq-bounded) by $M$ [converges](#def-g12-seq-limit) to some $\ell \leq M$, not necessarily to $M$.

**Theorem 20.20 (Limit of geometric sequences).**

Let $q \in \R$.

1. If $q > 1$ , then $q^n \to +\infty$ .
2. If $q = 1$ , then $q^n \to 1$ .
3. If $\abs{q} < 1$ , then $q^n \to 0$ .
4. 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](#ex-g12-seq-bernoulli)) gives $q^n \geq 1 + na \to +\infty$, and we conclude by comparison ([Theorem 20.16](#thm-g12-seq-squeeze)).

*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).](https://one-course.com/images/onecourse/chapters/math-2/g12-seq/fig-d2621466e91a.svg)

*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 un+1=f(un)u_{n+1} = f(u_n)un+1​=f(un​)).**

To study a [sequence](#def-g12-seq-sequence) defined by $u_{n+1} = f(u_n)$:

1. prove by induction that $(u_n)$ stays in an [interval](https://one-course.com/books/math/2/en/chapter/1-numbers-and-sets-of-numbers#def-g10-numbers-interval) $I$ on which $f$ is well behaved (and, often, that $(u_n)$ is [monotonic](#def-g12-seq-monotonic) );
2. deduce convergence from the monotone convergence theorem;
3. 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](https://one-course.com/books/math/2/en/chapter/21-limits-and-continuity#ch-g12-limcont) ); solve this [equation](https://one-course.com/books/math/2/en/chapter/2-algebra-equations-and-inequalities#def-g10-algebra-equation) and select the right [root](https://one-course.com/books/math/2/en/chapter/10-quadratic-functions-and-equations#def-g11-quad-discriminant) .

![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.](https://one-course.com/images/onecourse/chapters/math-2/g12-seq/fig-fce72bb54caf.svg)

*Staircase construction for $u_{n+1} = \sqrt{u_n + 2}$, $u_0 = 0$ ([Exercise 20.6](#exo-g12-seq-6)): each vertical step reads $f(u_n)$ on the curve, each horizontal step carries it back through $y = x$. The [sequence](#def-g12-seq-sequence) climbs to the [fixed point](https://one-course.com/books/math/2/en/chapter/3-functions#pb-g10-functions-1) $\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](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations), since

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

[Decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations) and [bounded below](#def-g12-seq-bounded), $(u_n)$ [converges](#def-g12-seq-limit) 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 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](#def-g12-seq-sequence) 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 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](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations).

$(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](#def-g12-seq-monotonic) (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](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-extrema), then increases. It is not [monotonic](#def-g12-seq-monotonic).

**Exercise 20.3 ★.**

Compute the limits of the [sequences](#def-g12-seq-sequence) 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 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](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#def-g11-seq-arithmetic) with $u_0 = 5$ and [common difference](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#def-g11-seq-arithmetic) $r = 3$, and $(v_n)$ the [geometric sequence](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#def-g11-seq-geometric) with $v_0 = 8$ and [common ratio](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#def-g11-seq-geometric) $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 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](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#def-g11-seq-geometric).

**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](#def-g12-seq-arith-geom) 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$.

1. Prove by induction that $0 \leq u_n \leq 2$ for all $n$ .
2. Show that $(u_n)$ is [increasing](#def-g12-seq-monotonic) .
3. Deduce that $(u_n)$ [converges](#def-g12-seq-limit) and determine its limit.

**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](#def-g12-seq-monotonic).

*3.* [Increasing](#def-g12-seq-monotonic) and [bounded above](#def-g12-seq-bounded) by $2$, $(u_n)$ [converges](#def-g12-seq-limit) 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$.

1. Justify that $u_{n+1} = 0.6\,u_n + 1$ .
2. Let $v_n = u_n - 2.5$ . Show that $(v_n)$ is [geometric](#def-g12-seq-arith-geom) and deduce an explicit formula for $u_n$ .
3. Determine the long-term quantity of drug in the body.

**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](#def-g12-seq-arith-geom) 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}$.

1. Show by induction that $u_n > 1$ for all $n \in \N$ .
2. Show that $v_n = \dfrac{1}{u_n - 1}$ defines an [arithmetic sequence](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#def-g11-seq-arithmetic) .
3. Deduce explicit formulas for $v_n$ and $u_n$ , and the limit of $(u_n)$ .

**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](#def-g12-seq-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](#def-g12-seq-arith-geom) with [common difference](https://one-course.com/books/math/2/en/chapter/13-sequences-a-first-course#def-g11-seq-arithmetic) $\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}$.

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

**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](#def-g12-seq-sequence) $(H_n)$ is [increasing](#def-g12-seq-monotonic) (each step adds $\frac{1}{n+1} > 0$) and the subsequence $H_{2^k}$ is unbounded, so $(H_n)$ is not [bounded above](#def-g12-seq-bounded). [Increasing](#def-g12-seq-monotonic) and unbounded, it tends to $+\infty$ ([Theorem 20.18](#thm-g12-seq-monotone)).

**Exercise 20.10 ★★★.**

*(Adjacent [sequences](#def-g12-seq-sequence).)* Two [sequences](#def-g12-seq-sequence) $(a_n)$ and $(b_n)$ are *adjacent* if $(a_n)$ is [increasing](#def-g12-seq-monotonic), $(b_n)$ is [decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations), and $b_n - a_n \to 0$.

1. Show that for all $n$ , $a_n \leq b_n$ . (Hint: study the monotonicity of $(b_n - a_n)$ .)
2. Show that adjacent [sequences](#def-g12-seq-sequence) both converge, to the same limit.
3. Application: show that the [sequences](#def-g12-seq-sequence) $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](https://one-course.com/books/math/2/en/chapter/23-exponential-and-logarithm#ch-g12-exp) .)

**Solution of Exercise 20.10.**

*1.* The [sequence](#def-g12-seq-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](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations); since $d_n \to 0$, we get $d_n \geq 0$ for all $n$ (a [decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations) [sequence](#def-g12-seq-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](#def-g12-seq-monotonic) [sequence](#def-g12-seq-sequence) $(a_n)$ is [bounded above](#def-g12-seq-bounded), so it [converges](#def-g12-seq-limit) to some $\ell$. Similarly $(b_n)$, [decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations) and [bounded below](#def-g12-seq-bounded) by $a_0$, [converges](#def-g12-seq-limit) to some $\ell'$. Then $\ell' - \ell = \lim (b_n - a_n) = 0$, so $\ell = \ell'$.

*3.* $(a_n)$ is (strictly) [increasing](#def-g12-seq-monotonic) 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](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations). Finally $b_n - a_n = \frac{1}{n\,n!} \to 0$. The two [sequences](#def-g12-seq-sequence) 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](#thm-g12-seq-induction)), the monotone convergence theorem ([Theorem 20.18](#thm-g12-seq-monotone)), 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.**

1. Prove by induction: $1 + 3 + 5 + \dots + (2n - 1) = n^2$ (the staircase of odd numbers, drawn in the Middle School volume, now certified).
2. Prove by induction that $2^n > n$ for every $n \in \N$ .
3. Prove Bernoulli’s inequality by induction: for $x \geq 0$ and $n \in \N$ , $(1 + x)^n \geq 1 + nx$ .
4. 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.
5. 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)$.

6. Compute $x_1$ , $x_2$ , $x_3$ as exact fractions (old friends).
7. 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$.
8. Show that $(x_n)$ is strictly [decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations) (compute $x_{n+1} - x_n$ and use question 7).
9. Invoke the monotone convergence theorem: why does $(x_n)$ converge to some limit $L \geq 1$ ?
10. Identify the limit: pass the recurrence to the limit ( [Proposition 20.14](#prop-g12-seq-operations) ) and conclude $L = \sqrt2$ . State the historical verdict: after two thousand years of faithful service, Heron’s recipe is *proved* to converge.
11. 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.
12. 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.**

13. [Exercise 20.9](#exo-g12-seq-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.)
14. By contrast, the [geometric](#def-g12-seq-arith-geom) sums $1 + \frac12 + \frac14 + \dots + \frac{1}{2^n} =  2 - \frac{1}{2^n}$ converge to $2$ ( [Theorem 20.20](#thm-g12-seq-geometric) ): the chocolate-bar intuition of the Middle School volume, finally a limit statement. Write out the two-line proof.
15. 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.)
16. 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](https://one-course.com/books/math/2/en/chapter/17-descriptive-statistics#def-g11-stat-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} .
$$

17. Compute $a_1, b_1, a_2, b_2$ (five decimals). What do you observe about the speed?
18. 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.
19. 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](#exo-g12-seq-10) that the two [sequences](#def-g12-seq-sequence) are adjacent: they share a common limit $M(1, 2)$ , the *arithmetic–geometric [mean](https://one-course.com/books/math/2/en/chapter/17-descriptive-statistics#def-g11-stat-mean)* .
20. 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 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](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations).

**9.** [Decreasing](https://one-course.com/books/math/2/en/chapter/3-functions#def-g10-functions-variations) and [bounded below](#def-g12-seq-bounded) (by $1$, since $x_n^2 > 2 > 1$ and $x_n > 0$): by the monotone convergence theorem, $(x_n)$ [converges](#def-g12-seq-limit) 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](#def-g12-seq-arith-geom) sum), and $\frac{1}{2^n} \to 0$ ([Theorem 20.20](#thm-g12-seq-geometric)), 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](#def-g12-seq-monotonic) and [bounded above](#def-g12-seq-bounded), 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](#def-g12-seq-sequence) 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](#def-g12-seq-sequence), slowest to fastest: the harmonic sums (glacial divergence), the [geometric](#def-g12-seq-arith-geom) 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.

1. Every nonempty subset of $\N$ has a smallest element; this property of $\N$ is taken as an axiom. [↩](#fnref-1)