University Mathematics — Year 1 · Bachelor jaar 1

11Sequences

Sequences were manipulated in the High School volume with the limit concept taken half on faith. Here the theory is rebuilt on the completeness of $\R$ (Chapter 10): every classical theorem — monotone convergence, adjacent sequences, Bolzano–Weierstrass, the Cauchy criterion — is a face of that single axiom. The chapter ends with the practical study of sequences defined by $u_{n+1} = f(u_n)$ .

11.1 Convergence

Definition 11.1 (Limit of a sequence)

A sequence $(u_n)$ of reals converges to $\ell \in \R$ when

\forall \varepsilon > 0,\ \exists N \in \N,\ \forall n \geq N, \qquad \abs{u_n - \ell} \leq \varepsilon .

One writes $u_n \to \ell$ or $\lim u_n = \ell$ . A sequence that does not converge (to any real) diverges. Divergence to $+\infty$ : $\forall M,\ \exists N,\ \forall n \geq N,\ u_n \geq M$ (similarly $-\infty$ ).

Example 11.2 (An $\varepsilon$ – $N$ proof, written out once)

Claim: $u_n = \dfrac{n^2 + 1}{2n^2 - 3} \to \dfrac12$ . First isolate the error:

\Bigl| u_n - \frac12 \Bigr| = \Bigl| \frac{2(n^2 + 1) - (2n^2 - 3)}{2(2n^2 - 3)} \Bigr| = \frac{5}{2\,\abs{2n^2 - 3}} = \frac{5}{2\,(2n^2 - 3)} \quad (n \geq 2).

Then dominate it by something simple: for $n \geq 2$ , $2n^2 - 3 \geq n^2$ , so the error is $\leq \frac{5}{2n^2} \leq \frac 5{2n}$ . Given $\varepsilon > 0$ , the Archimedean property provides $N \geq \max\bigl(2, \frac{5}{2\varepsilon}\bigr)$ ; for $n \geq N$ the error is $\leq \varepsilon$ . Done. The closing insight: an $\varepsilon$ – $N$ proof has exactly three moves — compute the error, bound it by a decreasing elementary expression, solve for the threshold — and after this chapter’s theorems (operations, squeeze) one almost never writes such a proof again: the theorems package the three moves once and for all.

Example 11.3 (Divergence to infinity, certified)

Claim: $u_n = n^2 - 100n \to +\infty$ . Factor the dominant term: $u_n = n^2\bigl(1 - \frac{100}{n}\bigr) \geq \frac{n^2}{2}$ for $n \geq 200$ . Given $M$ , take $N = \max\bigl(200, \lceil\sqrt{2M}\rceil\bigr)$ : for $n \geq N$ , $u_n \geq \frac{n^2}{2} \geq M$ . Two habits are on display: dominant-term factoring converts a competition ( $n^2$ against $-100n$ ) into a single scale times a factor tending to $1$ ; and the threshold may be huge ( $u_{100} = 0$ , the sequence is even negative before $n = 100$ ) — divergence to $+\infty$ is a statement about the tail, indifferent to any finite amount of misbehavior.

Proposition 11.4 (First properties)

The limit, if it exists, is unique.
A convergent sequence is bounded.
If $u_n \to \ell$ , every modification of finitely many terms leaves the convergence and the limit unchanged.

Proof. (1) If $u_n \to \ell$ and $u_n \to \ell'$ with $\ell \neq \ell'$ , take $\varepsilon = \frac{\abs{\ell - \ell'}}{3}$ : beyond the two thresholds, $\abs{\ell - \ell'} \leq \abs{\ell - u_n} + \abs{u_n - \ell'} \leq 2\varepsilon = \frac23 \abs{\ell - \ell'}$ , absurd.

(2) With $\varepsilon = 1$ : beyond $N$ , $\abs{u_n} \leq \abs\ell + 1$ ; the finitely many earlier terms are bounded too, so $\abs{u_n} \leq \max(\abs{u_0}, \dots, \abs{u_{N-1}}, \abs\ell + 1)$ .

(3) In detail: suppose $v_n = u_n$ for $n \geq n_0$ and $u_n \to \ell$ . Given $\varepsilon > 0$ , take the threshold $N$ for $(u_n)$ : for $n \geq \max(N, n_0)$ , $\abs{v_n - \ell} = \abs{u_n - \ell} \leq \varepsilon$ . So $v_n \to \ell$ : the definition quantifies only over $n \geq N$ , and any finite prefix can be overwritten at the cost of enlarging the threshold. (This is why hypotheses “for all large $n$ ” suffice everywhere in this chapter.) ∎

Theorem 11.5 (Operations on limits)

If $u_n \to \ell$ and $v_n \to m$ , then

u_n + v_n \to \ell + m, \qquad u_n v_n \to \ell m, \qquad \frac{u_n}{v_n} \to \frac{\ell}{m} \ (\text{if } m \neq 0), \qquad \abs{u_n} \to \abs\ell .

Proof. Sum: $\abs{(u_n + v_n) - (\ell + m)} \leq \abs{u_n - \ell} + \abs{v_n - m} \leq 2\varepsilon$ beyond the larger threshold. Product: write

u_n v_n - \ell m = (u_n - \ell)\,v_n + \ell\,(v_n - m);

$(v_n)$ is bounded by some $B$ (Proposition 11.4), so the right side is $\leq B\abs{u_n - \ell} + \abs{\ell}\,\abs{v_n - m}$ , arbitrarily small. Quotient: it suffices to treat $\frac 1{v_n}$ . With $\varepsilon = \frac{\abs m}{2}$ : beyond some $N_0$ , $\abs{v_n} \geq \frac{\abs m}{2}$ , so

\Bigl| \frac{1}{v_n} - \frac 1m \Bigr| = \frac{\abs{m - v_n}}{\abs{v_n m}} \leq \frac{2}{m^2}\,\abs{v_n - m} \longrightarrow 0 .

Absolute value: $\bigl|\abs{u_n} - \abs\ell\bigr| \leq \abs{u_n - \ell}$ (reverse triangle inequality, Proposition 3.2). ∎

Example 11.6 (Operations plus one algebraic trick)

Compute $\lim\,\bigl(\sqrt{n^2 + n} - n\bigr)$ . The two pieces separately tend to $+\infty$ : the operations theorem says nothing about their difference (an indeterminate form). Multiply by the conjugate:

\sqrt{n^2 + n} - n = \frac{(n^2 + n) - n^2}{\sqrt{n^2 + n} + n} = \frac{n}{\sqrt{n^2+n} + n} = \frac{1}{\sqrt{1 + \frac1n} + 1} .

Now everything converges: $\sqrt{1 + \frac1n} \to 1$ , because $0 \leq \sqrt{1 + h} - 1 = \frac{h}{\sqrt{1+h} + 1} \leq h$ (conjugate again, then squeeze with $h = \frac1n$ ); then the operations theorem gives the limit $\frac{1}{1 + 1} = \frac12$ . The closing insight: the operations theorem is not a calculator for all limits — indeterminate forms ( $\infty - \infty$ , $\frac00$ , $0 \times \infty$ , $1^\infty$ ) must first be transformed by algebra (conjugates, factoring the dominant term) until every piece converges; the systematic machine for resistant cases is the asymptotic expansion of Chapter 16.

Theorem 11.7 (Limits and order)

If $u_n \leq v_n$ for all large $n$ , and both converge, then $\lim u_n \leq \lim v_n$ . (Strict inequalities do not pass to the limit: $\frac 1n > 0$ but $\lim = 0$ .)
(Squeeze theorem) If $u_n \leq w_n \leq v_n$ for all large $n$ and $u_n, v_n \to \ell$ , then $w_n \to \ell$ .
If $u_n \to \ell > 0$ , then $u_n > \frac\ell2 > 0$ for all large $n$ .

Proof. (1) Suppose $\ell = \lim u_n > m = \lim v_n$ ; with $\varepsilon = \frac{\ell - m}{3}$ , large terms satisfy $v_n \leq m + \varepsilon < \ell - \varepsilon \leq u_n$ , contradicting $u_n \leq v_n$ .

(2) Beyond the thresholds: $\ell - \varepsilon \leq u_n \leq w_n \leq v_n \leq \ell + \varepsilon$ .

(3) is Definition 11.1 with $\varepsilon = \frac\ell2$ . ∎

Example 11.8 (Two squeezes)

(i) $\dfrac{\sin n}{n} \to 0$ : from $-\frac1n \leq \frac{\sin n}{n} \leq \frac1n$ , both walls collapsing on $0$ — no need to understand the erratic numerator at all. (ii) $(2^n + 3^n)^{1/n} \to 3$ : frame the inside,

3^n \leq 2^n + 3^n \leq 2\cdot3^n \quad\Longrightarrow\quad 3 \leq (2^n + 3^n)^{1/n} \leq 3\cdot 2^{1/n} ,

and $2^{1/n} = \eu^{\frac{\ln 2}{n}} \to 1$ (as for $5^{1/n}$ in Exercise 11.2): the squeeze delivers $3$ . The closing insight: a sum of competing exponentials behaves like its largest term — the smaller ones are absorbed by a harmless constant factor, which the $n$ -th root then erases.

11.2 Monotone sequences

Theorem 11.9 (Monotone limit theorem)

An increasing sequence bounded above converges, to $\sup\{u_n : n \in \N\}$ ; an increasing sequence not bounded above diverges to $+\infty$ . (Mirror statements for decreasing sequences.)

Proof. Let $s = \sup\{u_n\}$ (Theorem 10.2). Given $\varepsilon > 0$ , the $\varepsilon$ -characterization (Proposition 10.4) yields $N$ with $u_N > s - \varepsilon$ ; by monotonicity, $s - \varepsilon < u_N \leq u_n \leq s$ for all $n \geq N$ : convergence to $s$ . If unbounded: for every $M$ some $u_N > M$ , and monotonicity keeps all later terms above $M$ . ∎

Example 11.10 (The monotone theorem as an existence machine)

Let $u_n = \prod_{k=1}^{n} \bigl(1 + \frac{1}{2^k}\bigr)$ . Each factor exceeds $1$ , so $(u_n)$ is increasing. Bounded above? Take logarithms and use $\ln(1 + x) \leq x$ (Example 14.20 anticipates it; or the crude $1 + x \leq \eu^x$ from the High School volume):

\ln u_n = \sum_{k=1}^{n} \ln\Bigl(1 + \frac{1}{2^k}\Bigr) \leq \sum_{k=1}^{n} \frac{1}{2^k} < 1 ,

so $u_n < \eu$ . Increasing and bounded: $(u_n)$ converges to some $\ell \in \intoc{u_1}{\eu}$ — a perfectly well-defined real number with no closed form in sight ( $\ell = 2.384\dots$ ). The closing insight: the monotone limit theorem is the cheapest existence machine in analysis; it named $\eu$ itself (Example 11.12 below), and in Chapter 17 it will decide the convergence of every positive series by mere boundedness.

Theorem 11.11 (Adjacent sequences)

Let $(a_n)$ be increasing, $(b_n)$ decreasing, with $b_n - a_n \to 0$ . Then both converge, to a common limit $\ell$ , and $a_n \leq \ell \leq b_n$ for all $n$ .

Proof. First, $a_n \leq b_n$ for all $n$ : the sequence $(b_n - a_n)$ is decreasing and tends to $0$ , so it is $\geq 0$ (a negative term would freeze it below $0$ ). Then $(a_n)$ is increasing and bounded above by $b_0$ : it converges to some $\ell$ (Theorem 11.9); likewise $(b_n) \to \ell'$ ; and $\ell' - \ell = \lim (b_n - a_n) = 0$ . The inequalities $a_n \leq \ell \leq b_n$ follow from monotonicity ( $\ell = \sup a_k \geq a_n$ , etc.). ∎

Adjacent sequences: (a_n) climbs, (b_n) descends, and the gap between them shrinks to 0. Each interval [a_n, b_n] contains all later ones, and the common limit is the unique point left in every interval — the picture behind the dichotomy proofs of Bolzano–Weierstrass below and of the intermediate value theorem in . — Adjacent sequences: $(a_n)$ climbs, $(b_n)$ descends, and the gap between them shrinks to $0$ . Each interval $\intcc{a_n}{b_n}$ contains all later ones, and the common limit $\ell$ is the unique point left in every interval — the picture behind the dichotomy proofs of Bolzano–Weierstrass below and of the intermediate value theorem in Chapter 13.

Example 11.12 (The number $\eu$ )

Set $a_n = \sum_{k=0}^{n} \frac{1}{k!}$ and $b_n = a_n + \frac{1}{n \cdot n!}$ ( $n \geq 1$ ). Then $(a_n)$ increases; and

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)$ decreases, and $b_n - a_n \to 0$ : adjacent. Their common limit is (by definition here) the number $\eu \approx 2.71828$ ; the inequalities $a_n < \eu < b_n$ are sharp enough to prove $\eu \notin \Q$ (Exercise 11.9).

11.3 Subsequences and Bolzano–Weierstrass

Definition 11.13 (Subsequence)

A subsequence of $(u_n)$ is a sequence $(u_{\varphi(n)})$ where $\varphi \colon \N \to \N$ is strictly increasing (note $\varphi(n) \geq n$ , by induction).

Proposition 11.14

If $u_n \to \ell$ ( $\ell \in \R$ or $\pm\infty$ ), every subsequence tends to $\ell$ . Consequently, a sequence with two subsequences of different limits diverges. Conversely, if $(u_{2n})$ and $(u_{2n+1})$ both converge to the same $\ell$ , then $u_n \to \ell$ .

Proof. Beyond the threshold $N$ for $(u_n)$ , all indices $\varphi(n) \geq n \geq N$ qualify (the inequality $\varphi(n) \geq n$ is the induction noted in Definition 11.13: $\varphi(0) \geq 0$ , and $\varphi(n+1) > \varphi(n) \geq n$ forces $\varphi(n+1) \geq n + 1$ ). For the converse: given $\varepsilon$ , take the two thresholds $N_0$ (evens) and $N_1$ (odds); an arbitrary index $n \geq \max(2N_0, 2N_1 + 1)$ is either even, $n = 2k$ with $k \geq N_0$ , or odd, $n = 2k+1$ with $k \geq N_1$ — in both cases $\abs{u_n - \ell} \leq \varepsilon$ : every index is covered by one of the two subsequences, and that is the whole point. ∎

Example 11.15 (Subsequential limits)

For $u_n = (-1)^n \frac{n}{n+1}$ : the even subsequence tends to $1$ , the odd one to $-1$ , so the sequence diverges — but it does so in an organized way, clustering around the two values $\pm 1$ . For $u_n = \cos\frac{2\pi n}{3}$ : the three subsequences of indices $3k$ , $3k + 1$ , $3k + 2$ are constant, equal to $1$ , $-\frac12$ , $-\frac12$ ; the set of subsequential limits is $\{1, -\frac12\}$ . The closing insight: a bounded sequence converges exactly when it has a single subsequential limit (Exercise 11.8); divergence of a bounded sequence always means at least two clusters, and Bolzano–Weierstrass below guarantees there is at least one.

Theorem 11.16 (Bolzano–Weierstrass)

Every bounded sequence of reals has a convergent subsequence.

Proof. Let $u_n \in \intcc{a}{b}$ for all $n$ . Build nested segments by dichotomy: set $\intcc{a_0}{b_0} = \intcc{a}{b}$ ; given $\intcc{a_k}{b_k}$ containing $u_n$ for infinitely many $n$ , one of its two halves still contains $u_n$ for infinitely many $n$ — call it $\intcc{a_{k+1}}{b_{k+1}}$ . The sequences $(a_k)$ , $(b_k)$ are adjacent ( $b_k - a_k = \frac{b-a}{2^k} \to 0$ ), with common limit $\ell$ (Theorem 11.11).

Extract: choose $\varphi(0)$ with $u_{\varphi(0)} \in \intcc{a_0}{b_0}$ , then, inductively, $\varphi(k+1) > \varphi(k)$ with $u_{\varphi(k+1)} \in \intcc{a_{k+1}}{b_{k+1}}$ — possible since that segment contains infinitely many terms. Then $a_k \leq u_{\varphi(k)} \leq b_k$ , and the squeeze theorem gives $u_{\varphi(k)} \to \ell$ . ∎

Remark 11.17 (What Bolzano–Weierstrass does, and does not, say)

It does say: from boundedness alone, some subsequence converges — existence with no formula, as the dichotomy proof makes clear (nothing tells us which indices survive). It does not say the limit is unique: $((-1)^n)$ has subsequences converging to $1$ and to $-1$ , and the set of subsequential limits can even be infinite (Example 11.15, and all of the Cantor set in Problem 12.1). It does not survive unboundedness: $(n)$ has no convergent subsequence at all — though one can always extract a subsequence tending to $+\infty$ or $-\infty$ from any unbounded sequence (choose $\varphi(k)$ with $u_{\varphi(k)} \geq k$ , say). Used correctly, the theorem is an existence pump: it appears at the crux of the Cauchy criterion below, of Heine’s theorem, and of the extreme value theorem — always to produce a point that no explicit construction offers.

11.4 Cauchy sequences and completeness

Definition 11.18

A sequence $(u_n)$ is a Cauchy sequence when its terms become arbitrarily close to each other:

\forall \varepsilon > 0,\ \exists N,\ \forall p, q \geq N, \qquad \abs{u_p - u_q} \leq \varepsilon .

Example 11.19 (Verifying the Cauchy property by hand)

Let $u_n = \sum_{k=0}^{n} \frac{\cos k}{2^k}$ — no monotonicity, no guessable limit. For $p > q$ :

\abs{u_p - u_q} = \Bigl| \sum_{k=q+1}^{p} \frac{\cos k}{2^k} \Bigr| \leq \sum_{k=q+1}^{p} \frac{1}{2^k} < \frac{1}{2^{q}} ,

by the triangle inequality, $\abs{\cos k} \leq 1$ and a finite geometric sum. Given $\varepsilon > 0$ , choose $N$ with $2^{-N} \leq \varepsilon$ : all gaps beyond $N$ are $\leq \varepsilon$ , the sequence is Cauchy, hence converges — to a limit nobody can name in closed form, which is exactly the point. The closing insight: geometric domination of the increments is the standard way to earn the Cauchy property, and Chapter 17 will bottle the argument as “absolute convergence implies convergence”.

Theorem 11.20 (Completeness of $\R$ )

A sequence of reals converges if and only if it is a Cauchy sequence.

Proof. ( $\Rightarrow$ ) If $u_n \to \ell$ : beyond the threshold for $\frac\varepsilon2$ , $\abs{u_p - u_q} \leq \abs{u_p - \ell} + \abs{\ell - u_q} \leq \varepsilon$ .

( $\Leftarrow$ ) Let $(u_n)$ be Cauchy. It is bounded: with $\varepsilon = 1$ , beyond $N$ all terms lie within $1$ of $u_N$ , and the head is finite. Extract: by Theorem 11.16, some subsequence $u_{\varphi(n)} \to \ell$ . Conclude: given $\varepsilon > 0$ , take $N$ (Cauchy, for $\frac\varepsilon2$ ) and $n \geq N$ with $\abs{u_{\varphi(n)} - \ell} \leq \frac\varepsilon2$ and $\varphi(n) \geq N$ ; then for every $p \geq N$ :

\abs{u_p - \ell} \leq \abs{u_p - u_{\varphi(n)}} + \abs{u_{\varphi(n)} - \ell} \leq \varepsilon . \qedhere

∎

Remark 11.21

The value of the criterion: it certifies convergence without naming the limit. It fails over $\Q$ (the decimal truncations of $\sqrt 2$ form a Cauchy sequence of rationals with no rational limit): completeness is a property of $\R$ , equivalent to the upper bound axiom. It is also the workhorse behind the convergence of series (Chapter 17).

Example 11.22 (A Cauchy sequence with an invisible limit)

Let $S_n = \sum_{k=1}^{n} \frac{1}{k^2}$ . For $p > q \geq 1$ :

S_p - S_q = \sum_{k=q+1}^{p} \frac{1}{k^2} \leq \sum_{k=q+1}^{p} \frac{1}{k(k-1)} = \sum_{k=q+1}^{p} \Bigl(\frac{1}{k-1} - \frac 1k\Bigr) = \frac 1q - \frac 1p < \frac 1q ,

so beyond $N > \frac1\varepsilon$ all gaps are $\leq \varepsilon$ : $(S_n)$ is Cauchy, hence converges. Notice what just happened: we proved that a specific real number exists without having any name for it. (It is $\frac{\pi^2}{6}$ — a celebrated identity of Euler, proved in the Year 2 volume; nothing in this chapter could tell us that.) This division of labor — existence now, identification later, if ever — is the Cauchy criterion’s whole point, and the engine of the theory of series in Chapter 17.

11.5 Recurrent sequences

Method 11.23 (Studying $u_{n+1} = f(u_n)$ )

Given $f$ and a starting point $u_0$ :

Stable interval: find an interval $I$ with $f(I) \subseteq I$ containing $u_0$ : then all $u_n \in I$ (by induction).
Candidate limits: if $u_n \to \ell \in I$ and $f$ is continuous at $\ell$ (Chapter 13), then $\ell$ is a fixed point: $f(\ell) = \ell$ . Solve $f(x) = x$ .
Monotonicity: if $f$ is increasing on $I$ , then $(u_n)$ is monotonic (increasing if $u_1 \geq u_0$ , decreasing otherwise); combined with boundedness, Theorem 11.9 concludes. If $f$ is decreasing, study the two subsequences $(u_{2n})$ and $(u_{2n+1})$ , which are monotonic for $f \circ f$ .
Error control: an inequality $\abs{f(x) - \ell} \leq k\abs{x - \ell}$ with $k < 1$ gives $\abs{u_n - \ell} \leq k^n \abs{u_0 - \ell} \to 0$ directly.

Example 11.24 (Heron’s method)

Let $u_0 = 2$ and $u_{n+1} = \dfrac12\Bigl(u_n + \dfrac{2}{u_n}\Bigr)$ : the ancient algorithm for $\sqrt 2$ .

Stability: for $x > 0$ , the arithmetic–geometric mean inequality gives $\frac12(x + \frac2x) \geq \sqrt{x \cdot \frac 2x} = \sqrt 2$ ; so $I = \intco{\sqrt 2}{+\infty}$ is stable and contains $u_1$ (indeed $u_1 = \frac32 \geq \sqrt 2$ ).
Monotonicity: for $x \geq \sqrt 2$ , $\;x - f(x) = \frac{x^2 - 2}{2x} \geq 0$ : the sequence decreases from $u_1$ on, and is bounded below by $\sqrt 2$ : it converges.
Limit: the fixed points solve $x = \frac12(x + \frac2x)$ , i.e. $x^2 = 2$ : on $I$ , $\ell = \sqrt 2$ .
Speed: $u_{n+1} - \sqrt 2 = \frac{(u_n - \sqrt2)^2}{2u_n} \leq \frac{(u_n - \sqrt 2)^2}{2\sqrt 2}$ : the number of correct digits roughly doubles at each step (quadratic convergence).

Heron’s iteration u_n+1 = 1/2 (u_n + 2/u_n ), drawn as a staircase between the graph of f and the diagonal y = x: from u_0 = 2, the iterates slide down to the fixed point √ 2. — Heron’s iteration $u_{n+1} = \frac12\bigl(u_n + \frac{2}{u_n}\bigr)$ , drawn as a staircase between the graph of $f$ and the diagonal $y = x$ : from $u_0 = 2$ , the iterates slide down to the fixed point $\sqrt 2$ .

Remark 11.25 (Common pitfalls with limits)

Four classics. (i) Small steps do not imply convergence: $u_{n+1} - u_n \to 0$ is far weaker than the Cauchy property — the harmonic sums $H_n$ have steps $\frac{1}{n+1} \to 0$ yet diverge to $+\infty$ (Exercise 11.5); the Cauchy condition controls $\abs{u_p - u_q}$ for all large pairs, not consecutive ones. (ii) Strict inequalities die in the limit: from $u_n < v_n$ for all $n$ one gets only $\lim u_n \leq \lim v_n$ (Theorem 11.7); $\frac1n > 0$ and yet $\lim = 0$ . (iii) Bounded is not convergent: $((-1)^n)$ is bounded and diverges; boundedness plus monotonicity converges, boundedness alone only guarantees a convergent subsequence (Theorem 11.16). (iv) The fixed-point equation comes second, not first: for $u_{n+1} = f(u_n)$ , solving $f(\ell) = \ell$ identifies the limit only after convergence is proved. The recurrence $u_{n+1} = 2u_n$ has the unique fixed point $\ell = 0$ , yet from $u_0 = 1$ the sequence runs to $+\infty$ : the equation $\ell = 2\ell$ was never entitled to a limit. Order of operations, always: existence first (Method 11.23, steps 1–3), identification second.

Example 11.26 (A decreasing $f$ : the golden recurrence)

Let $u_0 = 1$ and $u_{n+1} = \dfrac{1}{1 + u_n}$ . Here $f(x) = \frac{1}{1+x}$ is decreasing, so the sequence is not monotonic (it alternates around its limit); the contraction step of Method 11.23 is the right tool. Stability: if $x \in \intcc{\frac12}{1}$ then $1 + x \in \intcc{\frac32}{2}$ , so $f(x) \in \intcc{\frac12}{\frac23} \subseteq \intcc{\frac12}{1}$ , and $u_1 = \frac12$ puts the whole sequence there. Fixed point: $\ell = \frac{1}{1+\ell}$ with $\ell > 0$ gives $\ell^2 + \ell - 1 = 0$ , i.e.

\ell = \frac{\sqrt5 - 1}{2} = 0.6180\dots

(the golden ratio’s inverse). Contraction: for $x, y \in \intcc{\frac12}{1}$ ,

\abs{f(x) - f(y)} = \frac{\abs{x - y}}{(1+x)(1+y)} \leq \frac{\abs{x-y}}{(3/2)^2} = \frac49\,\abs{x - y} ,

so $\abs{u_n - \ell} \leq \bigl(\frac49\bigr)^{n-1}\abs{u_1 - \ell} \to 0$ : convergence, with geometric speed, no monotonicity needed. The closing insight: monotone methods and contraction methods split the recurrent world between them — increasing $f$ gives monotone orbits, decreasing $f$ gives alternating orbits tamed by a Lipschitz constant $< 1$ (the systematic theory is Exercise 14.11).

Remark 11.27 (Perspectives inside this volume)

Sequences are the measuring instrument the rest of the volume holds up to every object. In Chapter 12 they characterize closedness and compactness; in Chapter 13 they transport limits of functions; in Chapter 15 Riemann sums are sequences converging to the integral; Chapter 17 is the theory of one special class of sequences, the partial sums. Even the algebra chapters consume them: the iterates of a matrix in Chapter 21 form sequences whose behavior (convergence of $A^n$ ) is a linear-algebra question with this chapter’s vocabulary. The two theorems to carry everywhere: monotone limit (existence from order) and Bolzano–Weierstrass (existence from boundedness) — between them, nearly every limit in this book is born.

Remark 11.28 (Complex sequences)

A sequence $(z_n)$ of complex numbers converges to $\ell$ when $\abs{z_n - \ell} \to 0$ ; equivalently, when $\Re(z_n) \to \Re(\ell)$ and $\Im(z_n) \to \Im(\ell)$ (compare $\abs{z}$ with $\abs{\Re z} + \abs{\Im z}$ ). The theorems not involving order — operations, Bolzano–Weierstrass (extract twice), Cauchy criterion — carry over verbatim.

11.6 Exercises

Exercise 11.1 ★

Directly from Definition 11.1, prove that $\dfrac{2n+1}{n+3} \to 2$ , and that $(u_n) = ((-1)^n)$ diverges.

Solution

Solution of Exercise 11.1.

$\Bigl|\dfrac{2n+1}{n+3} - 2\Bigr| = \dfrac{5}{n+3}$ . Given $\varepsilon > 0$ , take $N > \frac 5\varepsilon - 3$ (Archimedes): for $n \geq N$ , $\frac{5}{n+3} \leq \varepsilon$ . Hence the limit is $2$ .

$((-1)^n)$ : its subsequences $(u_{2n}) = (1)$ and $(u_{2n+1}) = (-1)$ converge to different limits, so the sequence diverges (Proposition 11.14). (Directly: any candidate $\ell$ fails for $\varepsilon = \frac12$ , since consecutive terms are at distance $2$ .)

Exercise 11.2 ★

Compute the limits:

\frac{n^2 - 3n + 1}{2n^2 + 5}, \qquad \sqrt{n+1} - \sqrt n, \qquad \frac{2^n + n^3}{3^n - n^2}, \qquad \sqrt[n]{5}\ \Bigl(= 5^{1/n}\Bigr).

Solution

Solution of Exercise 11.2.

Dividing by $n^2$ : $\dfrac{1 - 3/n + 1/n^2}{2 + 5/n^2} \to \dfrac12$ .

$\sqrt{n+1} - \sqrt n = \dfrac{1}{\sqrt{n+1} + \sqrt n} \to 0$ (conjugate).

$\dfrac{2^n + n^3}{3^n - n^2} = \dfrac{(2/3)^n + n^3/3^n}{1 - n^2/3^n} \to \dfrac{0 + 0}{1 - 0} = 0$ , using $q^n \to 0$ for $\abs q < 1$ and the polynomial-vs-geometric comparison (Proposition 4.6).

$5^{1/n} = \eu^{\frac{\ln 5}{n}} \to \eu^0 = 1$ .

Exercise 11.3 ★

Prove the standard comparison: if $\abs{q} < 1$ then $q^n \to 0$ (write $\frac{1}{\abs q} = 1 + h$ , $h > 0$ , and use the Bernoulli inequality $(1+h)^n \geq 1 + nh$ , to be proved by induction). What are the behaviors for $q = 1$ , $q = -1$ , $\abs q > 1$ ?

Solution

Solution of Exercise 11.3.

Bernoulli: $(1+h)^n \geq 1 + nh$ for $h \geq -1$ , by induction — $(1+h)^{n+1} = (1+h)^n(1+h) \geq (1+nh)(1+h) = 1 + (n+1)h + nh^2 \geq 1 + (n+1)h$ .

For $0 < \abs q < 1$ : write $\frac{1}{\abs q} = 1 + h$ , $h > 0$ ; then $\abs{q}^n = \frac{1}{(1+h)^n} \leq \frac{1}{1 + nh} \to 0$ , and the squeeze gives $q^n \to 0$ (the case $q = 0$ is trivial). For $q = 1$ : constant sequence, limit $1$ . For $q = -1$ : diverges (Exercise 11.1). For $\abs q > 1$ : $\abs q^n = (1 + h)^n \geq 1 + nh \to +\infty$ , so $(q^n)$ is unbounded, hence divergent (to $+\infty$ if $q > 1$ ; with alternating signs, no limit, if $q < -1$ ).

Exercise 11.4 ★

Let $u_{n+1} = \frac{u_n + 3}{2}$ , $u_0 = 0$ . Find the fixed point $\ell$ , prove that $v_n = u_n - \ell$ is geometric, and give an explicit formula and the limit of $(u_n)$ .

Solution

Solution of Exercise 11.4.

Fixed point: $\ell = \frac{\ell + 3}{2}$ gives $\ell = 3$ . Then

v_{n+1} = u_{n+1} - 3 = \frac{u_n + 3}{2} - 3 = \frac{u_n - 3}{2} = \frac{v_n}{2}:

$(v_n)$ is geometric with ratio $\frac12$ , $v_0 = -3$ . So $u_n = 3 - \frac{3}{2^n} \to 3$ .

Exercise 11.5 ★★

(Harmonic series) Let $H_n = \sum_{k=1}^{n} \frac 1k$ . Prove that $H_{2n} - H_n \geq \frac12$ for all $n \geq 1$ , and conclude that $(H_n)$ is not a Cauchy sequence, hence diverges (to $+\infty$ , being increasing).

Solution

Solution of Exercise 11.5.

$H_{2n} - H_n = \sum_{k=n+1}^{2n} \frac 1k \geq n \cdot \frac{1}{2n} = \frac12$ (each of the $n$ terms is $\geq \frac{1}{2n}$ ). If $(H_n)$ were Cauchy, taking $\varepsilon = \frac13$ would force $\abs{H_{2n} - H_n} \leq \frac13$ for large $n$ : contradiction. An increasing non-convergent sequence diverges to $+\infty$ (Theorem 11.9): $H_n \to +\infty$ .

Exercise 11.6 ★★

Suppose $(u_{2n})$ , $(u_{2n+1})$ and $(u_{3n})$ all converge. Prove that $(u_n)$ converges. (Find common subsequences to equate the limits.)

Solution

Solution of Exercise 11.6.

Let $a = \lim u_{2n}$ , $b = \lim u_{2n+1}$ , $c = \lim u_{3n}$ . The sequence $(u_{6n})$ is a subsequence both of $(u_{2n})$ and of $(u_{3n})$ : its limit equals $a$ and $c$ , so $a = c$ . The sequence $(u_{6n+3})$ is a subsequence of $(u_{2n+1})$ (odd indices) and of $(u_{3n})$ (indices $6n + 3 = 3(2n+1)$ ): so $b = c$ . Hence $a = b$ , and Proposition 11.14 (evens and odds with equal limits) gives the convergence of $(u_n)$ .

Exercise 11.7 ★★

Study the sequence $u_0 = 0$ , $u_{n+1} = \sqrt{2 + u_n}$ : stability, monotonicity, limit. Then prove the error bound $\abs{u_n - 2} \leq \dfrac{2}{3^{\,n}}$ (show $2 - u_{n+1} = \dfrac{2 - u_n}{2 + \sqrt{2 + u_n}}$ and bound the denominator below by $3$ ).

Solution

Solution of Exercise 11.7.

Stability and bounds: $I = \intcc{0}{2}$ is stable: for $x \in I$ , $\sqrt{2 + x} \in \intcc{\sqrt 2}{2} \subseteq I$ ; and $u_0 = 0 \in I$ .

Monotonicity: $f(x) = \sqrt{2+x}$ is increasing and $u_1 = \sqrt 2 > u_0$ : by induction $(u_n)$ is increasing. Increasing and bounded above by $2$ : it converges (Theorem 11.9).

Limit: $\ell = \sqrt{2 + \ell}$ with $\ell \geq 0$ gives $\ell^2 - \ell - 2 = 0$ , so $\ell = 2$ .

Error bound: multiplying by the conjugate,

2 - u_{n+1} = 2 - \sqrt{2 + u_n} = \frac{4 - (2 + u_n)}{2 + \sqrt{2+u_n}} = \frac{2 - u_n}{2 + \sqrt{2 + u_n}} \leq \frac{2 - u_n}{3},

since $\sqrt{2 + u_n} \geq \sqrt 2 > 1$ . By induction from $2 - u_0 = 2$ : $\;0 \leq 2 - u_n \leq \frac{2}{3^n}$ .

Exercise 11.8 ★★

Let $(u_n)$ be bounded, such that every convergent subsequence of $(u_n)$ has the same limit $\ell$ . Prove $u_n \to \ell$ . (Contradiction plus Bolzano–Weierstrass.)

Solution

Solution of Exercise 11.8.

Suppose $(u_n)$ does not converge to $\ell$ : for some $\varepsilon_0 > 0$ , infinitely many indices satisfy $\abs{u_n - \ell} > \varepsilon_0$ ; they form a subsequence $(u_{\varphi(n)})$ . This subsequence is bounded, so by Bolzano–Weierstrass (Theorem 11.16) it has a convergent sub-subsequence, whose limit $\ell'$ satisfies $\abs{\ell' - \ell} \geq \varepsilon_0$ (pass the inequality to the limit, Theorem 11.7). But a sub-subsequence of $(u_n)$ is a convergent subsequence of $(u_n)$ , so by hypothesis $\ell' = \ell$ : contradiction.

Exercise 11.9 ★★★

With the notation of Example 11.12, suppose $\eu = \frac pq$ with $p, q \in \N^*$ . Using $a_q < \eu < b_q = a_q + \frac{1}{q\, q!}$ , multiply by $q!$ and derive a contradiction between two integers. Conclude: $\eu$ is irrational.

Solution

Solution of Exercise 11.9.

Suppose $\eu = \frac pq$ , $q \geq 1$ . The strict inequalities $a_q < \eu < a_q + \frac{1}{q\,q!}$ (strict since $(a_n)$ is strictly increasing and $(b_n)$ strictly decreasing) multiplied by $q!$ give

q!\,a_q \;<\; q!\,\frac pq \;<\; q!\,a_q + \frac 1q \leq q!\,a_q + 1.

Now $N = q!\,a_q = \sum_{k=0}^{q} \frac{q!}{k!}$ is an integer (each $\frac{q!}{k!}$ is a product of integers for $k \leq q$ ), and so is $q!\,\frac pq = (q-1)!\,p$ . The display thus places the integer $(q-1)!\,p$ strictly between $N$ and $N + \frac 1q \leq N + 1$ : an integer strictly inside $\intoo{N}{N+1}$ , which is impossible. Hence $\eu \notin \Q$ .

Exercise 11.10 ★★★

(Cesàro means) For a sequence $(u_n)_{n \geq 1}$ , set $c_n = \frac{u_1 + \dots + u_n}{n}$ .

Prove that $u_n \to \ell$ implies $c_n \to \ell$ (cut the sum at a threshold $N$ ; bound the head by a fixed quantity over $n$ , the tail by $\varepsilon$ ).
Show by example that the converse fails.
Deduce that if $u_{n+1} - u_n \to \ell$ , then $\frac{u_n}{n} \to \ell$ .

Solution

Solution of Exercise 11.10.

Let $\varepsilon > 0$ and $N$ with $\abs{u_k - \ell} \leq \frac{\varepsilon}{2}$ for $k > N$ . For $n > N$ :

$\abs{c_n - \ell} = \Bigl|\frac{\sum_{k=1}^{n}(u_k - \ell)}{n}\Bigr| \leq \frac{\sum_{k=1}^{N} \abs{u_k - \ell}}{n} + \frac{n - N}{n}\cdot\frac{\varepsilon}{2} \leq \frac{C}{n} + \frac{\varepsilon}{2},$

where $C = \sum_{k=1}^N \abs{u_k - \ell}$ is fixed. For $n$ large, $\frac Cn \leq \frac\varepsilon2$ : then $\abs{c_n - \ell} \leq \varepsilon$ .
$u_n = (-1)^n$ : diverges, yet $c_n \to 0$ (partial sums bounded by $1$ , divided by $n$ ).
Apply (1) to the sequence $v_n = u_{n+1} - u_n \to \ell$ : its Cesàro mean is $\frac{u_{n+1} - u_1}{n} \to \ell$ (telescoping), and $\frac{u_{n+1}}{n} = \frac{u_{n+1} - u_1}{n} + \frac{u_1}{n} \to \ell$ ; renormalizing indices ( $\frac{u_n}{n} = \frac{u_n}{n-1}\cdot\frac{n-1}{n}$ ) gives $\frac{u_n}{n} \to \ell$ .

Exercise 11.11 ★★★

Let $(u_n)$ satisfy $0 \leq u_{m+n} \leq u_m + u_n$ for all $m, n$ (subadditivity). Prove that $\bigl(\frac{u_n}{n}\bigr)$ converges to $\inf_{n \geq 1} \frac{u_n}{n}$ . (For fixed $m$ , write $n = qm + r$ and bound $\frac{u_n}{n}$ using $u_n \leq q\,u_m + u_r$ .)

Solution

Solution of Exercise 11.11.

Let $L = \inf_{n \geq 1} \frac{u_n}{n} \geq 0$ , and $\varepsilon > 0$ . Choose $m$ with $\frac{u_m}{m} \leq L + \varepsilon$ . Every $n$ writes $n = qm + r$ , $0 \leq r < m$ ; subadditivity (iterated) gives $u_n \leq q\,u_m + u_r$ , so

\frac{u_n}{n} \leq \frac{q m}{n}\cdot\frac{u_m}{m} + \frac{u_r}{n} \leq \frac{u_m}{m} + \frac{\max(u_0, \dots, u_{m-1})}{n} \leq L + \varepsilon + \frac{C_m}{n},

using $qm \leq n$ . For $n$ large, $\frac{C_m}{n} \leq \varepsilon$ : thus $L \leq \frac{u_n}{n} \leq L + 2\varepsilon$ for all large $n$ , which is the convergence to $L$ .

Exercise 11.12 ★★★

Using the density of the subgroup $\Z + 2\pi\Z$ of $(\R, +)$ (Exercise 10.9), prove that the sequence $(\sin n)_{n \in \N}$ is dense in $\intcc{-1}{1}$ — in particular it diverges.

Solution

Solution of Exercise 11.12.

The subgroup $G = \Z + 2\pi\Z$ of $(\R, +)$ is dense: it is not $\alpha\Z$ , since $1 = p\alpha$ , $2\pi = q\alpha$ would make $2\pi = \frac qp$ rational — and $\pi \notin \Q$ (admitted here; a proof is sketched in Chapter 15). By Exercise 10.9, $G$ is dense in $\R$ .

Let now $y \in \intcc{-1}{1}$ and $\theta = \arcsin y$ . By density, for every $\varepsilon > 0$ there are $n \in \Z$ , $k \in \Z$ with $\abs{(n + 2\pi k) - \theta} \leq \varepsilon$ , i.e. $n$ is within $\varepsilon$ of $\theta - 2\pi k$ ; then, $\sin$ being $2\pi$ -periodic and $1$ -Lipschitz ( $\abs{\sin a - \sin b} \leq \abs{a - b}$ , from the mean value inequality of Chapter 14),

\abs{\sin n - y} = \abs{\sin(n + 2\pi k) - \sin\theta} \leq \abs{n + 2\pi k - \theta} \leq \varepsilon .

One detail: $n$ ranges over $\Z$ , but $\sin(-n) = -\sin n$ and $y$ was arbitrary in $\intcc{-1}{1}$ , so nonnegative indices suffice (replace $(n, y)$ by $(-n, -y)$ if needed). Hence $\{\sin n : n \in \N\}$ is dense in $\intcc{-1}{1}$ ; a dense-in-a-segment sequence has subsequences approaching distinct values, so it diverges.

11.7 Problem: Cesàro, Stolz, and the slow fall of the sine

Problem 11.1

Weekend problem — the Cesàro–Stolz theorem and the asymptotics $u_n \sim \sqrt{3/n}$ for $u_{n+1} = \sin u_n$

The Cesàro–Stolz theorem is the discrete l’Hospital rule: to find the limit of a quotient $a_n/b_n$ , it suffices to find the limit of the quotient of increments $(a_{n+1} - a_n)/(b_{n+1} - b_n)$ . This problem proves the theorem, harvests classical limits with it, and then aims it at a famous target: the sequence $u_{n+1} = \sin u_n$ , which creeps to $0$ at the exactly computable speed $u_n \sim \sqrt{3/n}$ . Two facts from the High School volume are granted here and re-proved honestly later in this volume: the tangent-line inequality

\tag{G1} \eu^{u} \geq 1 + u \quad (u \in \R),

re-proved by convexity in Chapter 14, and the sine bracketing

\tag{G2} x - \frac{x^3}{6} \;\leq\; \sin x \;\leq\; x - \frac{x^3}{6} + \frac{x^5}{120} \quad (0 \leq x \leq 1), \qquad \abs{\sin x} \leq \abs{x} \quad (x \in \R),

re-proved by Taylor’s formula in Chapter 16.

Part I — Sums without closed formulas.

Using $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ and $1^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$ , compute $\lim \frac{1 + 2 + \dots + n}{n^2}$ and $\lim \frac{1^2 + \dots + n^2}{n^3}$ .
Let $T_n = \sum_{k=1}^n \sqrt k$ , for which no closed formula exists. Prove the bracketing

$\frac{1}{2\sqrt 2}\,n^{3/2} \;\leq\; T_n \;\leq\; n^{3/2}$

(keep only the terms $k > \frac n2$ for the lower bound). So $T_n$ has the order $n^{3/2}$ — but which constant? Hold the question until question 8.
(Telescoping lemma) Let $(b_n)$ be strictly increasing and suppose that for all $k \geq N$ ,

$m \;\leq\; \frac{a_{k+1} - a_k}{b_{k+1} - b_k} \;\leq\; M .$

Prove that $m \leq \dfrac{a_n - a_N}{b_n - b_N} \leq M$ for every $n > N$ .

Part II — The Cesàro–Stolz theorem. Let $(b_n)$ be strictly increasing with $b_n \to +\infty$ , and suppose $\dfrac{a_{n+1} - a_n}{b_{n+1} - b_n} \to \ell \in \R$ .

Fix $\varepsilon > 0$ . Show there is $N$ such that $\ell - \varepsilon \leq \dfrac{a_n - a_N}{b_n - b_N} \leq \ell + \varepsilon$ for all $n > N$ .
Establish, for $n > N$ , the identity

$\frac{a_n}{b_n} - \ell = \frac{a_N - \ell\,b_N}{b_n} + \Bigl(1 - \frac{b_N}{b_n}\Bigr) \Bigl(\frac{a_n - a_N}{b_n - b_N} - \ell\Bigr),$

and conclude the theorem: $\dfrac{a_n}{b_n} \to \ell$ .
Prove the $+\infty$ variant: if $\dfrac{a_{n+1} - a_n}{b_{n+1} - b_n} \to +\infty$ (same hypotheses on $(b_n)$ ), then $\dfrac{a_n}{b_n} \to +\infty$ .
Take $b_n = n$ : recover the Cesàro mean theorem of Exercise 11.10. Then show the converse of Cesàro–Stolz fails: for $a_n = (-1)^n$ , $b_n = n$ , the quotient $a_n/b_n$ converges while the quotient of increments does not. Stolz is a one-way street.

Part III — First dividends.

Prove $(1+h)^{3/2} - 1 = \dfrac{3h + 3h^2 + h^3}{(1+h)^{3/2} + 1}$ by conjugation, deduce $n\bigl((1 + \tfrac1n)^{3/2} - 1\bigr) \to \tfrac32$ , and conclude with Cesàro–Stolz:

$T_n = \sum_{k=1}^{n} \sqrt k \;\sim\; \tfrac23\, n^{3/2} ,$

resolving the cliffhanger of question 2.
From (G1) alone, derive the logarithm bracketing

$\frac{t}{1 + t} \;\leq\; \ln(1 + t) \;\leq\; t \qquad (t > -1)$

(apply (G1) at $u = \ln(1+t)$ and at $u = -t/(1+t)$ ).
Show that $b_n = \ln n$ is strictly increasing with $\ln n \to +\infty$ , and prove with Cesàro–Stolz and question 9 that

$H_n = \sum_{k=1}^{n} \frac 1k \;\sim\; \ln n .$

(The finer structure $H_n = \ln n + \gamma + o(1)$ is the weekend problem of Chapter 17.)
(From ratios to roots) Let $u_n > 0$ with $\frac{u_{n+1}}{u_n} \to L > 0$ . Using question 9, show $\ln\frac{u_{n+1}}{u_n} \to \ln L$ ; apply Cesàro to conclude $\frac{\ln u_n}{n} \to \ln L$ , then, with (G1), that $u_n^{1/n} \to L$ . Application: compute $\lim\,\binom{2n}{n}^{1/n}$ .

Part IV — The slow fall of the sine. Let $u_0 \in \R$ and $u_{n+1} = \sin u_n$ .

From (G2), show $0 < \sin x < x$ for $0 < x \leq 1$ . Deduce: $u_1 \in \intcc{-1}{1}$ ; if $u_1 = 0$ the sequence is zero from rank $1$ ; and if $u_1 > 0$ (the case $u_1 < 0$ being symmetric, $\sin$ odd), then $(u_n)_{n \geq 1}$ is strictly decreasing, positive, and converges to $0$ (identify the limit via $\ell = \sin \ell$ , using $\abs{\sin a - \sin b} \leq \abs{a - b}$ , itself a consequence of (G2) and the product-to-sum formula).
Assume from now on $u_1 \in \intoc{0}{1}$ . Show by squeezing, using (G2):

$\frac{\sin u_n}{u_n} \to 1 \qquad\text{and}\qquad \frac{u_n - \sin u_n}{u_n^{3}} \to \frac16 .$
Prove the factorization

$w_n := \frac{1}{u_{n+1}^{2}} - \frac{1}{u_n^{2}} = \frac{u_n - \sin u_n}{u_n^{3}} \cdot \frac{u_n + \sin u_n}{u_n} \cdot \Bigl(\frac{u_n}{\sin u_n}\Bigr)^{2},$

and deduce $w_n \to \frac13$ .
Conclude with Exercise 11.10 (increments version) that $\frac{1}{n\,u_n^{2}} \to \frac13$ , then, by a conjugation argument for the square root, the headline:

$\sqrt n\;u_n \longrightarrow \sqrt 3 , \qquad\text{i.e.}\qquad u_n \sim \sqrt{\frac 3n} .$
Quantify the slowness: show that eventually $\sqrt{2/n} \leq u_n \leq 2/\sqrt n$ , so that reaching $u_n \leq 10^{-2}$ requires more than $20\,000$ iterations (about $30\,000$ , by the asymptotics). Contrast with Heron’s method (Example 11.24) and explain the structural reason: at the fixed point $0$ , the slope of $\sin$ is $1$ (a neutral fixed point), while error-halving iterations need a slope of modulus $< 1$ .
Show that for every starting point $u_0 \in \R$ , either $u_n = 0$ from rank $1$ on, or $\abs{u_n} \sim \sqrt{3/n}$ — the fall is universal, only the sign remembers $u_0$ .

Part V — The general principle. The sine is one instance of a machine.

Let $u_n > 0$ , $u_n \to 0$ , and $\dfrac{u_n - u_{n+1}}{u_n^{2}} \to a > 0$ . Prove successively: $\frac{u_{n+1}}{u_n} \to 1$ ; then $\frac{1}{u_{n+1}} - \frac{1}{u_n} \to a$ ; then $n\,u_n \to \frac1a$ .
(Exact model) For $u_{n+1} = \dfrac{u_n}{1 + u_n}$ , $u_0 > 0$ : show $\frac{1}{u_n}$ is arithmetic, solve exactly, and check question 18’s conclusion against the exact formula.
For $u_{n+1} = u_n \eu^{-u_n}$ , $u_0 > 0$ : show $u_n \to 0$ , use (G1) to squeeze $\frac{1 - \eu^{-t}}{t}$ between $\frac{1}{1+t}$ and $1$ for $t > 0$ , and conclude $u_n \sim \frac 1n$ .
(Cubic contact, squared telescope) Let $u_n > 0$ , $u_n \to 0$ , $\dfrac{u_n - u_{n+1}}{u_n^{3}} \to a > 0$ . Adapt question 14’s factorization to show $\frac{1}{u_{n+1}^2} - \frac{1}{u_n^2} \to 2a$ , and conclude $n\,u_n^{2} \to \frac{1}{2a}$ . Check that $a = \frac16$ recovers Part IV.

Part VI — Limits of the method, and morals.

Show that the hypothesis $b_n \to +\infty$ cannot be dropped: for $a_n = 2 - 2^{-n}$ and $b_n = 1 - 2^{-n}$ , the increment quotient tends to $1$ while $\frac{a_n} {b_n} \to 2$ . Point to the exact line of question 5’s proof that breaks.
(Stolz twice) Prove $\sum_{k=1}^{n} H_k \sim n \ln n$ (one application of Cesàro–Stolz, then question 10; bound $(n+1)\ln(n+1) - n\ln n$ using question 9).
(Geometric means) If $u_n > 0$ and $u_n \to \ell > 0$ , show $(u_1 u_2 \cdots u_n)^{1/n} \to \ell$ ; if $u_n \to +\infty$ , show $(u_1 \cdots u_n)^{1/n} \to +\infty$ . Deduce $(n!)^{1/n} \to +\infty$ .
Synthesis, one sentence each: (i) where exactly did completeness enter this problem; (ii) in what sense is Cesàro–Stolz a discrete l’Hospital rule (its differential twin rests on the mean value theorem of Chapter 14); (iii) state the heuristic linking the contact order of $f$ at a neutral fixed point to the decay exponent of $u_{n+1} = f(u_n)$ ; (iv) trace the constant $3$ of $\sqrt{3/n}$ back through the pipeline $\frac16 \to \frac13 \to 3$ .

Solution

Solution of Problem 11.1.

1. $\dfrac{n(n+1)/2}{n^2} = \dfrac{1 + 1/n}{2} \to \dfrac12$ , and $\dfrac{n(n+1)(2n+1)/6}{n^3} = \dfrac{(1 + 1/n)(2 + 1/n)}{6} \to \dfrac13$ .

2. Upper: each of the $n$ terms is $\leq \sqrt n$ , so $T_n \leq n\sqrt n$ . Lower: the terms with $k > \frac n2$ number at least $\frac n2$ , and each is $\geq \sqrt{n/2}$ :

T_n \geq \frac n2 \sqrt{\frac n2} = \frac{n^{3/2}}{2\sqrt 2} .

3. For $k \geq N$ , since $b_{k+1} - b_k > 0$ : $m(b_{k+1} - b_k) \leq a_{k+1} - a_k \leq M(b_{k+1} - b_k)$ . Summing for $k = N, \dots, n - 1$ , both sides telescope:

m\,(b_n - b_N) \leq a_n - a_N \leq M\,(b_n - b_N),

and dividing by $b_n - b_N > 0$ gives the claim.

4. By definition of the limit there is $N$ with $\ell - \varepsilon \leq \frac{a_{k+1} - a_k}{b_{k+1} - b_k} \leq \ell + \varepsilon$ for all $k \geq N$ ; question 3 with $m = \ell - \varepsilon$ , $M = \ell + \varepsilon$ transfers the bracketing to $\frac{a_n - a_N}{b_n - b_N}$ .

5. Expanding the right side of the identity:

\frac{a_N - \ell b_N}{b_n} + \frac{a_n - a_N}{b_n} - \ell\,\frac{b_n - b_N}{b_n} = \frac{a_n - \ell b_n}{b_n} = \frac{a_n}{b_n} - \ell .

By question 4 the second factor of the product is bounded by $\varepsilon$ in absolute value, and $0 < 1 - \frac{b_N}{b_n} \leq 1$ for large $n$ , so

\Bigl|\frac{a_n}{b_n} - \ell\Bigr| \leq \frac{\abs{a_N - \ell b_N}}{b_n} + \varepsilon \leq 2\varepsilon

as soon as $b_n \geq \frac{\abs{a_N - \ell b_N}}{\varepsilon}$ , which happens eventually since $b_n \to +\infty$ . Hence $\frac{a_n}{b_n} \to \ell$ : the Cesàro–Stolz theorem.

6. Given $M$ , choose $N$ with $\frac{a_{k+1} - a_k}{b_{k+1} - b_k} \geq M$ for $k \geq N$ ; the lower half of question 3 gives $a_n - a_N \geq M(b_n - b_N)$ , so

\frac{a_n}{b_n} \geq \frac{a_N}{b_n} + M\Bigl(1 - \frac{b_N}{b_n}\Bigr) \longrightarrow M .

Beyond some rank, $\frac{a_n}{b_n} \geq M - 1$ ; as $M$ was arbitrary, $\frac{a_n}{b_n} \to +\infty$ .

7. With $b_n = n$ and $a_n = u_1 + \dots + u_n$ : the increment quotient is $u_{n+1} \to \ell$ , so the Cesàro mean $\frac{a_n}{n}$ tends to $\ell$ : part (1) of Exercise 11.10. With $a_n = u_n$ : the increment quotient is $u_{n+1} - u_n$ , giving part (3). Converse: $a_n = (-1)^n$ , $b_n = n$ has $\frac{a_n}{b_n} \to 0$ , yet $a_{n+1} - a_n = \pm 2$ alternates: the increment quotient has no limit.

8. Conjugation:

\bigl((1+h)^{3/2} - 1\bigr)\bigl((1+h)^{3/2} + 1\bigr) = (1+h)^3 - 1 = 3h + 3h^2 + h^3 .

For $h = \frac1n$ : $n\bigl((1 + \frac1n)^{3/2} - 1\bigr) = \frac{3 + 3/n + 1/n^2}{(1 + 1/n)^{3/2} + 1}$ , and $1 \leq (1 + \frac1n)^{3/2} \leq (1 + \frac1n)^2 \to 1$ (squeeze), so the denominator tends to $2$ and the expression to $\frac32$ . Now Stolz with $a_n = T_n$ , $b_n = n^{3/2}$ (strictly increasing, $\to +\infty$ ):

\frac{\sqrt{n+1}}{(n+1)^{3/2} - n^{3/2}} = \frac{\sqrt{n+1}}{\sqrt n} \cdot \frac{1}{n\bigl((1 + \frac1n)^{3/2} - 1\bigr)} \longrightarrow 1 \cdot \frac{2}{3},

hence $T_n \sim \frac23\,n^{3/2}$ . (The bracketing of question 2 had trapped the constant in $\intcc{0.35}{1}$ ; Stolz pins it.)

9. (G1) at $u = \ln(1+t)$ : $1 + t = \eu^{\ln(1+t)} \geq 1 + \ln(1+t)$ , so $\ln(1+t) \leq t$ . (G1) at $u = -\frac{t}{1+t}$ : $\eu^{-t/(1+t)} \geq 1 - \frac{t}{1+t} = \frac{1}{1+t} > 0$ ; taking $\ln$ (increasing): $-\frac{t}{1+t} \geq -\ln(1+t)$ , i.e. $\ln(1+t) \geq \frac{t}{1+t}$ .

10. $\ln$ is strictly increasing (Proposition 4.1), and $\ln(2^k) = k\ln 2$ is unbounded, so $\ln n \to +\infty$ . Increments: with $t = \frac1n$ in question 9,

\frac 1{n+1} = \frac{1/n}{1 + 1/n} \leq \ln\Bigl(1 + \frac1n\Bigr) \leq \frac1n \quad\Longrightarrow\quad \frac{n}{n+1} \leq \frac{1/(n+1)}{\ln(1 + 1/n)} \leq 1 ,

so the increment quotient $\frac{H_{n+1} - H_n}{\ln(n+1) - \ln n}$ tends to $1$ ; Stolz gives $H_n \sim \ln n$ .

11. Set $x_n = \frac{u_{n+1}}{u_n} \to L$ and $t_n = \frac{x_n}{L} - 1 \to 0$ . Question 9: $\frac{t_n}{1 + t_n} \leq \ln(1 + t_n) \leq t_n$ , so $\ln x_n - \ln L = \ln(1 + t_n) \to 0$ by squeezing. Cesàro (question 7) applied to $(\ln x_k)$ :

\frac1n \sum_{k=0}^{n-1} \ln x_k = \frac{\ln u_n - \ln u_0}{n} \longrightarrow \ln L ,

so $\frac{\ln u_n}{n} \to \ln L$ . With $h_n = \frac{\ln u_n}{n} - \ln L \to 0$ : $u_n^{1/n} = L\,\eu^{h_n}$ , and (G1) squeezes $1 + h_n \leq \eu^{h_n} \leq \frac{1}{1 - h_n}$ (for $h_n < 1$ ), so $\eu^{h_n} \to 1$ and $u_n^{1/n} \to L$ . Application: $u_n = \binom{2n}{n}$ gives

\frac{u_{n+1}}{u_n} = \frac{(2n+1)(2n+2)}{(n+1)^2} = \frac{2(2n+1)}{n+1} \longrightarrow 4 , \qquad\text{so}\qquad \binom{2n}{n}^{1/n} \to 4 .

12. For $0 < x \leq 1$ , (G2) gives $\sin x \geq x(1 - \frac{x^2}{6}) \geq \frac{5x}{6} > 0$ and

x - \sin x \geq \frac{x^3}{6} - \frac{x^5}{120} = x^3\Bigl(\frac16 - \frac{x^2}{120}\Bigr) \geq \frac{19}{120}\,x^3 > 0 :

thus $0 < \sin x < x$ on $\intoc{0}{1}$ . Always $u_1 = \sin u_0 \in \intcc{-1}{1}$ . If $u_1 = 0$ , then $u_n = 0$ for $n \geq 1$ . If $u_1 \in \intoc{0}{1}$ : by induction $0 < u_{n+1} = \sin u_n < u_n \leq 1$ , so $(u_n)_{n\geq1}$ is strictly decreasing and bounded below by $0$ : it converges to some $\ell \in \intco{0}{1}$ (Theorem 11.9). The product-to-sum formula and (G2) give $\abs{\sin a - \sin b} = 2\abs{\cos \frac{a+b}{2}}\,\abs{\sin\frac{a-b}{2}} \leq \abs{a - b}$ , so $u_{n+1} = \sin u_n \to \sin \ell$ : $\ell = \sin\ell$ . If $\ell > 0$ then $\sin\ell < \ell$ : impossible. So $u_n \to 0$ .

13. Dividing (G2) by $u_n > 0$ :

1 - \frac{u_n^2}{6} \leq \frac{\sin u_n}{u_n} \leq 1 - \frac{u_n^2}{6} + \frac{u_n^4}{120} \leq 1 ,

and $u_n \to 0$ squeezes $\frac{\sin u_n}{u_n} \to 1$ . Dividing $x - \sin x$ by $x^3$ :

\frac16 - \frac{u_n^2}{120} \leq \frac{u_n - \sin u_n}{u_n^3} \leq \frac16 \longrightarrow \frac16 .

14. Since $u_{n+1} = \sin u_n$ :

w_n = \frac{u_n^2 - \sin^2 u_n}{u_n^2 \sin^2 u_n} = \frac{(u_n - \sin u_n)(u_n + \sin u_n)}{u_n^2 \sin^2 u_n} = \frac{u_n - \sin u_n}{u_n^3}\cdot \frac{u_n + \sin u_n}{u_n}\cdot \Bigl(\frac{u_n}{\sin u_n}\Bigr)^{2}

(check the powers of $u_n$ : $3 + 1 + (-4)$ against the $u_n^2$ downstairs and $u_n^4$ upstairs). By question 13 the three factors tend to $\frac16$ , $2$ , $1$ : $w_n \to \frac13$ .

15. $v_n = \frac{1}{u_n^2}$ has increments $v_{n+1} - v_n = w_n \to \frac13$ , so $\frac{v_n}{n} \to \frac13$ by Exercise 11.10 (3): $n u_n^2 \to 3$ . Then

\abs{\sqrt n\,u_n - \sqrt 3} = \frac{\abs{n u_n^2 - 3}}{\sqrt n\,u_n + \sqrt 3} \leq \frac{\abs{n u_n^2 - 3}}{\sqrt 3} \longrightarrow 0 :

$\sqrt n\,u_n \to \sqrt 3$ , i.e. $u_n \sim \sqrt{3/n}$ .

16. Since $n u_n^2 \to 3$ , eventually $2 \leq n u_n^2 \leq 4$ , i.e. $\sqrt{2/n} \leq u_n \leq 2/\sqrt n$ . If $u_n \leq 10^{-2}$ with $n$ in that range, then $2/n \leq 10^{-4}$ : $n \geq 20\,000$ ; and $\sqrt{3/n} = 10^{-2}$ at $n = 30\,000$ . Heron’s method squares the error at each step — the digit count doubles — because at its fixed point the relevant slope is $< 1$ in modulus (indeed the iteration is contracting). Here $\sin' 0 = \cos 0 = 1$ : the fixed point is neutral, no geometric contraction exists, and the decay is governed by the first nonlinear term $-\frac{x^3}{6}$ , hence polynomial. One step of Heron gains more accuracy than ten thousand steps of the sine.

17. For arbitrary $u_0$ : $u_1 = \sin u_0 \in \intcc{-1}{1}$ . If $u_1 = 0$ the sequence vanishes from rank $1$ . If $u_1 > 0$ , Part IV applies verbatim. If $u_1 < 0$ , set $v_n = -u_n$ : oddness of $\sin$ gives $v_{n+1} = -\sin u_n = \sin(-u_n) = \sin v_n$ with $v_1 \in \intoc{0}{1}$ , so $v_n \sim \sqrt{3/n}$ , i.e. $u_n \sim -\sqrt{3/n}$ . In all cases $\abs{u_n} \sim \sqrt{3/n}$ (or the sequence is eventually $0$ ): the fall is universal, only the sign remembers the start.

18. First $\frac{u_{n+1}}{u_n} = 1 - \frac{u_n - u_{n+1}}{u_n^2}\,u_n \to 1 - a \cdot 0 = 1$ . Then

\frac{1}{u_{n+1}} - \frac{1}{u_n} = \frac{u_n - u_{n+1}}{u_n u_{n+1}} = \frac{u_n - u_{n+1}}{u_n^2}\cdot\frac{u_n}{u_{n+1}} \longrightarrow a \cdot 1 = a ,

and Exercise 11.10 (3) gives $\frac{1}{n u_n} \to a$ , i.e. $n u_n \to \frac1a$ .

19. $v_n = \frac{1}{u_n}$ : $v_{n+1} = \frac{1 + u_n}{u_n} = v_n + 1$ , so $v_n = v_0 + n$ and

u_n = \frac{u_0}{1 + n u_0} , \qquad n u_n = \frac{n u_0}{1 + n u_0} \longrightarrow 1 .

Lemma check: $u_n - u_{n+1} = \frac{u_n^2}{1 + u_n}$ , so $\frac{u_n - u_{n+1}}{u_n^2} = \frac{1}{1 + u_n} \to 1 = a$ , and question 18 predicts $n u_n \to 1$ : exact agreement.

20. Positivity by induction ( $\eu^{-u} > 0$ ); decreasing since $\eu^{-u_n} < 1$ for $u_n > 0$ ; hence $u_n \to \ell \geq 0$ (Theorem 11.9). Continuity bridge: with $h_n = \ell - u_n \to 0$ , $\eu^{-u_n} = \eu^{-\ell} \eu^{h_n} \to \eu^{-\ell}$ by the (G1) squeeze $1 + h_n \leq \eu^{h_n} \leq \frac{1}{1 - h_n}$ ; so $\ell = \ell\, \eu^{-\ell}$ , and $\ell > 0$ would force $\eu^{-\ell} = 1$ , false: $\ell = 0$ . For $t > 0$ , (G1) gives $\eu^{-t} \geq 1 - t$ and $\eu^{-t} \leq \frac{1}{1 + t}$ , so

\frac{1}{1 + t} \leq \frac{1 - \eu^{-t}}{t} \leq 1 .

With $t = u_n$ : $\frac{u_n - u_{n+1}}{u_n^2} = \frac{1 - \eu^{-u_n}}{u_n} \to 1$ . Question 18 with $a = 1$ : $n u_n \to 1$ , so $u_n \sim \frac1n$ .

21. As in question 18, $\frac{u_{n+1}}{u_n} = 1 - \frac{u_n - u_{n+1}}{u_n^3}\,u_n^2 \to 1$ . Then

\frac{1}{u_{n+1}^2} - \frac{1}{u_n^2} = \frac{(u_n - u_{n+1})(u_n + u_{n+1})}{u_n^2 u_{n+1}^2} = \frac{u_n - u_{n+1}}{u_n^3}\cdot \frac{u_n + u_{n+1}}{u_n}\cdot \Bigl(\frac{u_n}{u_{n+1}}\Bigr)^2 \longrightarrow a \cdot 2 \cdot 1 = 2a ,

and Exercise 11.10 (3) gives $\frac{1}{n u_n^2} \to 2a$ : $n u_n^2 \to \frac{1}{2a}$ . For the sine, $a = \frac16$ (question 13): $n u_n^2 \to 3$ , exactly Part IV.

22. Increments: $a_{n+1} - a_n = 2^{-n} - 2^{-n-1} = 2^{-n-1} = b_{n+1} - b_n$ , so the increment quotient is constantly $1$ . Yet $\frac{a_n}{b_n} = \frac{2 - 2^{-n}}{1 - 2^{-n}} \to 2 \neq 1$ . The proof of question 5 breaks at the boundary term: $\frac{a_N - \ell b_N}{b_n} \to 0$ needed $b_n \to +\infty$ ; here (with $\ell = 1$ ) $a_N - b_N = 1$ and $b_n \to 1$ , so the term tends to $1$ — precisely the residual gap $2 - 1$ .

23. Stolz with $A_n = \sum_{k=1}^n H_k$ and $B_n = n\ln n$ : $B_{n+1} - B_n = \ln(n+1) + n\ln(1 + \frac1n) > 0$ and $B_n \to +\infty$ . By question 9, $\frac{n}{n+1} \leq n\ln(1 + \frac1n) \leq 1$ , so $B_{n+1} - B_n = \ln(n+1) + \theta_n$ with $\frac12 \leq \theta_n \leq 1$ . Hence

\frac{A_{n+1} - A_n}{B_{n+1} - B_n} = \frac{H_{n+1}}{\ln(n+1)}\cdot \frac{1}{1 + \theta_n/\ln(n+1)} \longrightarrow 1 \cdot 1 = 1

(question 10 for the first factor; $\theta_n$ bounded and $\ln(n+1) \to \infty$ for the second). Stolz concludes: $\sum_{k=1}^n H_k \sim n\ln n$ .

24. If $u_n \to \ell > 0$ : as in question 11, $\ln u_n \to \ln\ell$ (question 9 squeeze on $\ln\frac{u_n}{\ell}$ ), so the Cesàro means $\frac1n\sum_{k=1}^n \ln u_k \to \ln\ell$ , and the exponential bridge of question 11 gives $(u_1\cdots u_n)^{1/n} = \exp\bigl(\frac1n\sum\ln u_k\bigr) \to \ell$ . If $u_n \to +\infty$ : for any $M$ , eventually $u_n \geq \eu^M$ , so $\ln u_n \geq M$ : $\ln u_n \to +\infty$ ; the $+\infty$ Cesàro (question 6, $b_n = n$ ) gives $\frac1n\sum \ln u_k \to +\infty$ , and (G1) ( $\eu^s \geq 1 + s$ ) sends the geometric mean to $+\infty$ . With $u_n = n$ : $(n!)^{1/n} \to +\infty$ .

25. (i) Completeness entered only through the monotone limit theorem, to produce the limits in questions 12 and 20; the Cesàro–Stolz theorem itself is pure $\varepsilon$ -management, valid over $\Q$ . (ii) Stolz replaces $\lim \frac{a_n}{b_n}$ by $\lim$ of the quotient of increments, exactly as l’Hospital replaces $\lim\frac fg$ by $\lim\frac{f'}{g'}$ — the differential twin rests on the mean value theorem of Chapter 14. (iii) Heuristic: if $f(x) = x - a\,x^{p+1} + o(x^{p+1})$ at the neutral fixed point $0$ , then $\frac{1}{u_{n+1}^p} - \frac{1}{u_n^p} \to pa$ and $u_n \sim (pan)^{-1/p}$ : contact of order $p + 1$ yields decay $n^{-1/p}$ — the flatter the graph against the diagonal, the slower the fall. (iv) The constant: (G2) supplies the cubic coefficient $\frac16$ ; the factorization of question 14 doubles it into the telescope increment $\frac13$ ; Cesàro turns $\frac{1}{u_n^2}$ into $\frac n3$ ; inverting and taking roots delivers $\sqrt{3/n}$ .

Terms defined in this chapter

See all 395 terms in the glossary