Chapter IV · Limits of functions of a positive integral variable

The general principle of convergence

§§83–84 40 min

Cauchy’s criterion decides whether a sequence converges by comparing its terms with each other, without knowing the limit in advance.

Why this matters

To prove ϕ(n)→l\phi(n) \to l from the definition you must first know ll. Often you do not. What is 1−12+13−14+⋯1 - \tfrac12 + \tfrac13 - \tfrac14 + \cdots? What is ∑(sin⁡k)/k\sum (\sin k)/k? The monotone-sequence theorem of §69 avoids the problem, but only for monotone sequences. §83 and §84 give a test that works for every sequence: it converges if and only if its terms eventually stay close to each other. This general principle of convergence, usually called Cauchy’s criterion, is the standard tool for proving that series converge in Chapter VIII, and it is the property that makes the real numbers “complete”.

The idea

If a sequence tends to ll, its tail is crowded into a thin strip around ll, so any two late terms are close to each other. Cauchy’s criterion says the converse holds as well: if any two late terms are close to each other, there is a number they all crowd around. The test looks only at differences ϕ(n2)−ϕ(n1)\phi(n_2) - \phi(n_1), so no candidate limit is needed.

For a tail starting at n0n_0, “every two terms differ by less than δ\delta” means the same as “the largest and smallest terms of the tail differ by less than δ\delta”: the tail fits into a strip of width less than δ\delta, wherever that strip happens to be.

Explore Squeeze the tail without knowing the limit

Try this. For the partial sums of 1−12+13−⋯1 - \tfrac12 + \tfrac13 - \cdots, set δ=0.1\delta = 0.1 and move n0n_0 until the strip turns green. Make δ\delta smaller and repeat (use “Smallest n0n_0”, and show more terms when needed). Then try the harmonic sums and (−1)n(1+1/n)(-1)^n(1 + 1/n). Only at the end, reveal the limit.

sn=1−12+13−⋯+(−1)n+1ns_n = 1 - \tfrac12 + \tfrac13 - \cdots + \tfrac{(-1)^{n+1}}{n}
nφ(n)
  • the tail’s spread, from n₀ = 5
  • its highest and lowest terms
  • terms (hollow: before n₀)
For 5≤n≤2005 \le n \le 200 the terms lie between 0.616667 and 0.783333: spread 0.1667 ≥ δ=0.1\delta = 0.1. For instance ∣ϕ(6)−ϕ(5)∣=0.1667|\phi(6) - \phi(5)| = 0.1667, which is not below δ. The smallest n0n_0 that works here is 9.
What to notice

For the convergent sequences, every δ\delta has an n0n_0: the strip can be made as thin as you like by starting late enough, and the limit, when revealed, sits inside every strip. For the harmonic sums the spread of a tail never drops below about 1.381.38 (it grows with the number of terms checked), and for (−1)n(1+1/n)(-1)^n(1 + 1/n) it never drops below 22. You decided convergence without ever being told the limit.

Precise statements

Theorem The general principle of convergence Hardy: Theorem 1, §§83–84

A sequence ϕ(n)\phi(n) tends to a limit if and only if, for every δ>0\delta > 0, there is an n0(δ)n_0(\delta) such that

∣ϕ(n2)−ϕ(n1)∣<δfor all n2>n1≥n0(δ).|\phi(n_2) - \phi(n_1)| < \delta \quad \text{for all } n_2 > n_1 \ge n_0(\delta).

Hardy first proves this for bounded sequences (§83), then removes the word “bounded” (§84) by showing that the condition forces boundedness. Applied to the partial sums sns_n of a series, with sn2−sn1=un1+1+⋯+un2s_{n_2} - s_{n_1} = u_{n_1 + 1} + \cdots + u_{n_2}, it becomes a criterion for series.

Corollary Cauchy’s criterion for series Hardy: Theorem 2, §84

The series u1+u2+⋯u_1 + u_2 + \cdots converges if and only if, for every δ>0\delta > 0, there is an n0n_0 such that

∣un1+1+un1+2+⋯+un2∣<δfor all n2>n1≥n0.|u_{n_1 + 1} + u_{n_1 + 2} + \cdots + u_{n_2}| < \delta \quad \text{for all } n_2 > n_1 \ge n_0.

In words: a series converges exactly when every block of terms far enough out has a small sum, however long the block. Taking blocks of one term (n2=n1+1n_2 = n_1 + 1) recovers “un→0u_n \to 0”, and the harmonic series fails the test with long blocks: 1n+1+⋯+12n≥12\tfrac1{n+1} + \cdots + \tfrac1{2n} \ge \tfrac12.

Proofs

Proof The condition is necessary
Strategy

If both terms are within 12δ\tfrac12\delta of the limit, they are within δ\delta of each other.

Use the definition with 12δ\tfrac12\delta

If ϕ(n)→l\phi(n) \to l, there is n0n_0 with ∣ϕ(n)−l∣<12δ|\phi(n) - l| < \tfrac12\delta for all n≥n0n \ge n_0.

Triangle inequality

For n2>n1≥n0n_2 > n_1 \ge n_0: ∣ϕ(n2)−ϕ(n1)∣≤∣ϕ(n2)−l∣+∣l−ϕ(n1)∣<12δ+12δ=δ|\phi(n_2) - \phi(n_1)| \le |\phi(n_2) - l| + |l - \phi(n_1)| < \tfrac12\delta + \tfrac12\delta = \delta.

The other direction is the substantial one. It needs a number to converge to, and that number has to come from somewhere: from the completeness of the real numbers, here in the form of the upper and lower limits.

Proof The condition forces boundedness
Strategy

Fix one late term. Every later term is within 11 of it, and only finitely many terms come before it.

Take δ=1\delta = 1

The condition gives n0n_0 with ∣ϕ(n2)−ϕ(n1)∣<1|\phi(n_2) - \phi(n_1)| < 1 for n2>n1≥n0n_2 > n_1 \ge n_0.

Fix n1=n0n_1 = n_0

Then ϕ(n0)−1<ϕ(n)<ϕ(n0)+1\phi(n_0) - 1 < \phi(n) < \phi(n_0) + 1 for every n>n0n > n_0.

Add the finitely many early terms

The terms ϕ(1),…,ϕ(n0)\phi(1), \dots, \phi(n_0) have a largest and a smallest value. Together with the previous step, all terms lie between min⁡(ϕ(1),…,ϕ(n0))−1\min(\phi(1), \dots, \phi(n_0)) - 1 and max⁡(ϕ(1),…,ϕ(n0))+1\max(\phi(1), \dots, \phi(n_0)) + 1.

Proof The condition is sufficient
Strategy

The sequence is bounded, so it has an upper limit Λ\Lambda and a lower limit λ\lambda, and it converges if and only if λ=Λ\lambda = \Lambda (§82). If λ<Λ\lambda < \Lambda, infinitely many terms are near Λ\Lambda and infinitely many near λ\lambda, so arbitrarily late pairs of terms differ by nearly Λ−λ\Lambda - \lambda: the condition fails.

Suppose λ<Λ\lambda < \Lambda and choose a small δ\delta

Take δ=14(Λ−λ)>0\delta = \tfrac14(\Lambda - \lambda) > 0.

Late terms near both ends

By properties (3) and (4) of §82, infinitely many nn have ϕ(n)>Λ−δ\phi(n) > \Lambda - \delta, and infinitely many have ϕ(n)<λ+δ\phi(n) < \lambda + \delta. So beyond any n0n_0 there are n1n_1 and n2n_2 (in either order) of each kind.

Their difference is large

For such a pair, ∣ϕ(n2)−ϕ(n1)∣>(Λ−δ)−(λ+δ)=Λ−λ−2δ=2δ>δ|\phi(n_2) - \phi(n_1)| > (\Lambda - \delta) - (\lambda + \delta) = \Lambda - \lambda - 2\delta = 2\delta > \delta.

Contradiction, so λ=Λ\lambda = \Lambda

For this δ\delta no n0n_0 can work, contradicting the hypothesis. Hence λ=Λ\lambda = \Lambda, and by §82 (5) the sequence tends to their common value.

The criterion for series is the theorem applied to ϕ(n)=sn\phi(n) = s_n.

Worked examples and exercises

Exercise The harmonic series fails Cauchy’s test ●○○ Hardy: §84

Use Cauchy’s criterion to prove again that ∑1/n\sum 1/n does not converge.

Hint
Take n1=nn_1 = n and n2=2nn_2 = 2n.

Solution

The block 1n+1+⋯+12n\dfrac{1}{n+1} + \cdots + \dfrac{1}{2n} has nn terms, each at least 12n\dfrac{1}{2n}, so its sum is at least 12\tfrac12. Take δ=12\delta = \tfrac12. Whatever n0n_0 is proposed, n1=n0n_1 = n_0 and n2=2n0n_2 = 2n_0 give sn2−sn1≥12s_{n_2} - s_{n_1} \ge \tfrac12. So the condition fails, and the series does not converge (its terms are positive, so it diverges to +∞+\infty).

Exercise The alternating harmonic series ●●○ Hardy: §84

Show that 1−12+13−14+⋯1 - \tfrac12 + \tfrac13 - \tfrac14 + \cdots converges, using Cauchy’s criterion and without finding its sum.

Hint
A block ±(1m−1m+1+1m+2−⋯)\pm\big(\tfrac1{m} - \tfrac1{m+1} + \tfrac1{m+2} - \cdots\big) of alternating decreasing terms lies between 00 and its first term. Group it in pairs to see this.

Solution

Let n2>n1n_2 > n_1 and m=n1+1m = n_1 + 1. Up to sign, the block is B=1m−1m+1+1m+2−⋯±1n2B = \tfrac1m - \tfrac1{m+1} + \tfrac1{m+2} - \cdots \pm \tfrac1{n_2}. Grouping in pairs from the start, (1m−1m+1)+(1m+2−1m+3)+⋯(\tfrac1m - \tfrac1{m+1}) + (\tfrac1{m+2} - \tfrac1{m+3}) + \cdots, every bracket is positive (and a single last term is positive), so B>0B > 0. Grouping from the second term, 1m−(1m+1−1m+2)−⋯\tfrac1m - (\tfrac1{m+1} - \tfrac1{m+2}) - \cdots, every bracket is positive and subtracted (a single last term −1n2-\tfrac1{n_2} is negative), so B≤1mB \le \tfrac1m. Hence ∣sn2−sn1∣≤1n1+1|s_{n_2} - s_{n_1}| \le \dfrac{1}{n_1 + 1}.

Given δ>0\delta > 0, take n0>1/δn_0 > 1/\delta. Then for n2>n1≥n0n_2 > n_1 \ge n_0, ∣sn2−sn1∣≤1/(n1+1)<δ|s_{n_2} - s_{n_1}| \le 1/(n_1 + 1) < \delta. By Cauchy’s criterion the series converges. (Its sum is log⁡2\log 2, proved in Chapter IX.)

Exercise A tail bound for ∑1/k2\sum 1/k^2 ●●○ Hardy: §84

Using 1k2<1k−1−1k\dfrac{1}{k^2} < \dfrac{1}{k-1} - \dfrac{1}{k} for k≥2k \ge 2, show that 0<sn2−sn1<1/n10 < s_{n_2} - s_{n_1} < 1/n_1 for the partial sums of ∑1/k2\sum 1/k^2, and deduce convergence from Cauchy’s criterion.

Hint
The bound telescopes.

Solution

1k−1−1k=1k(k−1)>1k2\dfrac1{k-1} - \dfrac1k = \dfrac{1}{k(k-1)} > \dfrac1{k^2}. Hence

sn2−sn1=∑k=n1+1n21k2<∑k=n1+1n2(1k−1−1k)=1n1−1n2<1n1.s_{n_2} - s_{n_1} = \sum_{k = n_1 + 1}^{n_2} \frac1{k^2} < \sum_{k = n_1 + 1}^{n_2} \Big(\frac1{k-1} - \frac1k\Big) = \frac1{n_1} - \frac1{n_2} < \frac1{n_1}.

Given δ\delta, any n0>1/δn_0 > 1/\delta makes this less than δ\delta for n2>n1≥n0n_2 > n_1 \ge n_0. (Comparison with ∑1/(k(k−1))\sum 1/(k(k-1)) would also do, but this proof needs nothing about positive series.)

Exercise Small steps are not enough ●●○ Hardy: §84

Give a sequence with ϕ(n+1)−ϕ(n)→0\phi(n+1) - \phi(n) \to 0 that does not converge, and explain which part of Cauchy’s condition it fails.

Hint
Try n\sqrt n, or the harmonic partial sums.

Solution

ϕ(n)=n\phi(n) = \sqrt n: ϕ(n+1)−ϕ(n)=1n+1+n→0\phi(n+1) - \phi(n) = \dfrac{1}{\sqrt{n+1} + \sqrt n} \to 0, but n→+∞\sqrt n \to +\infty. Cauchy’s condition controls all pairs n2>n1≥n0n_2 > n_1 \ge n_0, not only neighbours: here ϕ(4n)−ϕ(n)=n\phi(4n) - \phi(n) = \sqrt n is large. Many small steps can add up to a long walk.

Exercise Geometrically shrinking steps ●●● Hardy: §84

Suppose ∣ϕ(n+1)−ϕ(n)∣≤Crn|\phi(n+1) - \phi(n)| \le C r^n for all nn, where C>0C > 0 and 0<r<10 < r < 1. Show that ϕ(n)\phi(n) converges.

Hint
Write ϕ(n2)−ϕ(n1)\phi(n_2) - \phi(n_1) as a sum of consecutive steps and compare with a geometric series.

Solution

For n2>n1n_2 > n_1,

∣ϕ(n2)−ϕ(n1)∣≤∑n=n1n2−1∣ϕ(n+1)−ϕ(n)∣≤C(rn1+rn1+1+⋯ )=Crn11−r.|\phi(n_2) - \phi(n_1)| \le \sum_{n = n_1}^{n_2 - 1} |\phi(n+1) - \phi(n)| \le C(r^{n_1} + r^{n_1 + 1} + \cdots) = \frac{C r^{n_1}}{1 - r}.

Since rn→0r^{n} \to 0, given δ>0\delta > 0 there is n0n_0 with Crn0/(1−r)<δC r^{n_0}/(1 - r) < \delta, and then the same holds for every n1≥n0n_1 \ge n_0. By Cauchy’s criterion ϕ(n)\phi(n) converges. This is how iterative methods such as Heron’s square-root rule are often proved to converge, without knowing the answer in advance.

Check yourself

Check yourself Choose one

Which statement is Cauchy’s condition?

Why

The condition must control every pair of late terms, not just neighbours (options 1 and 2 only look at consecutive terms, and n\sqrt n satisfies the first from some point on without converging). The last option puts n0n_0 before δ\delta, which forces the sequence to be eventually constant.

Check yourself True or false?

If ϕ(n+1)−ϕ(n)→0\phi(n+1) - \phi(n) \to 0, then ϕ(n)\phi(n) converges.

Why

False. The partial sums of the harmonic series have steps 1/(n+1)→01/(n+1) \to 0 but diverge. The steps must be small in total over arbitrarily long stretches, which is what Cauchy’s condition demands.

Check yourself Enter a number

For the partial sums of 1−12+13−⋯1 - \tfrac12 + \tfrac13 - \cdots, the largest value of ∣sn2−sn1∣|s_{n_2} - s_{n_1}| over n2>n1n_2 > n_1 is 1/(n1+1)1/(n_1 + 1). What is the smallest n0n_0 that works in Cauchy’s condition for δ=0.01\delta = 0.01?

Why

We need 1/(n1+1)<0.011/(n_1 + 1) < 0.01 for every n1≥n0n_1 \ge n_0, that is n1+1>100n_1 + 1 > 100 for n1=n0n_1 = n_0: n0≥100n_0 \ge 100. With n0=99n_0 = 99 the pair n1=99n_1 = 99, n2=100n_2 = 100 gives exactly 1100\tfrac1{100}, which is not less than 0.010.01.

Check yourself Choose one

Where does the proof of sufficiency use a property of the real numbers that the rational numbers lack?

Why

Λ\Lambda and λ\lambda are bounds of sets of numbers, and their existence comes from Dedekind’s theorem. In the rationals the decimal approximations 1,1.4,1.41,…1, 1.4, 1.41, \dots of 2\sqrt 2 satisfy Cauchy’s condition but have no rational limit. That is why “complete” is the modern name for exactly this property.

Hardy’s language

The theoretical importance of the ‘general principle of convergence’ can hardly be overestimated.

— G. H. Hardy, §84

Summary

Summary
  • Cauchy’s criterion: ϕ(n)\phi(n) converges if and only if for every δ>0\delta > 0 there is n0n_0 with ∣ϕ(n2)−ϕ(n1)∣<δ|\phi(n_2) - \phi(n_1)| < \delta for all n2>n1≥n0n_2 > n_1 \ge n_0.
  • It needs no candidate limit: the tail must fit into some strip of width δ\delta, wherever that strip is.
  • Necessity is the triangle inequality. Sufficiency uses boundedness and the upper and lower limits: if λ<Λ\lambda < \Lambda, late terms near each end are far apart.
  • For series: ∑un\sum u_n converges iff every far-out block un1+1+⋯+un2u_{n_1+1} + \cdots + u_{n_2} has small sum. Small single steps are not enough.