Chapter VIII · The convergence of infinite series and infinite integrals

Cauchy's condensation test

§182 30 min

For decreasing terms, the series Σφ(n) behaves exactly like the much thinner series Σ2^nφ(2^n), which turns powers into geometric series and logarithms into powers.

Why this matters

The integral test needs a function ϕ(x)\phi(x) of a continuous variable and an integral we can evaluate. §182 gives a test with the same reach that needs neither: only the terms themselves, at the indices 1,2,4,8,16,…1, 2, 4, 8, 16, \dots. It is the argument Hardy used in §77 to show that ∑1/n\sum 1/n diverges, turned into a general theorem. It settles ∑n−s\sum n^{-s} in one line, and in Chapter IX it settles ∑1/(nlog⁡n)\sum 1/(n \log n) and ∑1/(n(log⁡n)2)\sum 1/(n(\log n)^2), where every power of nn is too coarse.

The idea

Group the terms in blocks of doubling length: the block 2k≤n<2k+12^k \le n < 2^{k+1} has 2k2^k terms. If the terms decrease, the largest term of the block is its first, ϕ(2k)\phi(2^k), and the smallest is its last. So the whole block is at most 2kϕ(2k)2^k\phi(2^k), and (shifting the blocks by one place) at least about half of the next such quantity. In other words the series behaves like the condensed series

ϕ(1)+2ϕ(2)+4ϕ(4)+8ϕ(8)+⋯=∑k2kϕ(2k),\phi(1) + 2\phi(2) + 4\phi(4) + 8\phi(8) + \cdots = \sum_k 2^k\phi(2^k),

which keeps only one term per block and multiplies it by the block length.

Explore Blocks of doubling length

Try this. With ϕ(n)=n−s\phi(n) = n^{-s} and s=1s = 1, compare each block with its rectangle in both modes, and read the table. Then try s=1.5s = 1.5, and the two logarithmic series.

ϕ(n)=n−1\phi(n) = n^{-1}, terms grouped in blocks of length 2k2^k
nφ(n)
  • terms φ(n), alternate blocks in two colours
  • rectangle of height ϕ(2k)\phi(2^k) over the block 2k≤n<2k+12^k \le n < 2^{k+1}
Compare each block with
kblock 2ᵏ ≤ n < 2ᵏ⁺¹2ᵏ φ(2ᵏ)
011
10.83331
20.75951
30.72541
40.7091
50.7011
Each block sum is at most 2kϕ(2k)2^k\phi(2^k), because the block has 2k2^k terms and the first is the largest. Adding up: 4.728 ≤ 6. So if the condensed series ∑2kϕ(2k)\sum 2^k\phi(2^k) converges, the partial sums of ∑ϕ(n)\sum\phi(n) are bounded. Here 2kϕ(2k)=(21−s)k=1k2^k\phi(2^k) = (2^{1-s})^k = 1^k: a geometric series, convergent exactly when s>1s > 1.
What to notice

For s=1s = 1 every rectangle has area exactly 11: the block sums neither shrink nor grow, so the series diverges. For s=1.5s = 1.5 the rectangle areas shrink by the factor 2−1/22^{-1/2} from block to block, a geometric series. In each mode the block sums are on the correct side of the rectangle areas: at most the upper ones, at least the lower ones.

Precise statements

Theorem Cauchy’s condensation test Hardy: §182

If ϕ(n)\phi(n) is positive and decreases as nn increases, then the series ∑ϕ(n)\sum \phi(n) and ∑2nϕ(2n)\sum 2^n\phi(2^n) are either both convergent or both divergent.

The test works with any integer base a≥2a \ge 2 in place of 22 (Examples LXXII, 1), but 22 is usually the most convenient.

Corollary ∑n−s\sum n^{-s} again Hardy: §182

∑n−s\sum n^{-s} converges if s>1s > 1 and diverges if s≤1s \le 1.

Indeed, for s>0s > 0 the condensed series is ∑2n2−ns=∑(21−s)n\sum 2^n 2^{-ns} = \sum (2^{1-s})^n, a geometric series with ratio 21−s2^{1-s}, which is less than 11 exactly when s>1s > 1. (For s≤0s \le 0 the terms do not tend to 00.) Condensation turns powers of nn into geometric series, and, as Chapter IX will show, powers of log⁡n\log n into powers of nn.

Proofs

Proof Cauchy’s condensation test
Strategy

Compare each block of terms with its largest term (for an upper bound) and with its smallest term (for a lower bound). Both comparisons produce the condensed series, so the two series have bounded partial sums together.

Upper bound: blocks 2k≤n<2k+12^k \le n < 2^{k+1}

The block has 2k2^k terms, each at most the first one, since ϕ\phi decreases:

ϕ(2)+ϕ(3)≤2ϕ(2),ϕ(4)+⋯+ϕ(7)≤4ϕ(4),…\phi(2) + \phi(3) \le 2\phi(2), \qquad \phi(4) + \cdots + \phi(7) \le 4\phi(4), \qquad \ldots

and in general ϕ(2k)+⋯+ϕ(2k+1−1)≤2kϕ(2k)\phi(2^k) + \cdots + \phi(2^{k+1} - 1) \le 2^k\phi(2^k).

So condensed convergence implies convergence

Adding the blocks k=0,1,…,Kk = 0, 1, \dots, K: ϕ(1)+⋯+ϕ(2K+1−1)≤∑k=0K2kϕ(2k)\phi(1) + \cdots + \phi(2^{K+1} - 1) \le \sum_{k=0}^{K} 2^k\phi(2^k). If the condensed series converges, the right side is bounded by its sum, so the partial sums of ∑ϕ(n)\sum\phi(n) (which increase) are bounded and the series converges.

Lower bound: blocks 2k<n≤2k+12^k < n \le 2^{k+1}

Now compare each block with its last, smallest term:

ϕ(3)+ϕ(4)≥2ϕ(4),ϕ(5)+⋯+ϕ(8)≥4ϕ(8),…\phi(3) + \phi(4) \ge 2\phi(4), \qquad \phi(5) + \cdots + \phi(8) \ge 4\phi(8), \qquad \ldots

and in general ϕ(2k+1)+⋯+ϕ(2k+1)≥2kϕ(2k+1)=12⋅2k+1ϕ(2k+1)\phi(2^k + 1) + \cdots + \phi(2^{k+1}) \ge 2^k\phi(2^{k+1}) = \tfrac12 \cdot 2^{k+1}\phi(2^{k+1}).

So condensed divergence implies divergence

Adding the blocks k=0,…,Kk = 0, \dots, K: ϕ(2)+⋯+ϕ(2K+1)≥12∑k=1K+12kϕ(2k)\phi(2) + \cdots + \phi(2^{K+1}) \ge \tfrac12 \sum_{k=1}^{K+1} 2^k\phi(2^k). If the condensed series diverges, the right side tends to ∞\infty, and so do the partial sums of ∑ϕ(n)\sum\phi(n).

Conclude

Both series have positive terms, so each either converges or diverges to ∞\infty. The two steps show that they do the same thing.

Notice the role of “decreasing”: it is what lets one term stand for a whole block. For terms that go up and down, a single term at n=2kn = 2^k says nothing about its neighbours.

Worked examples and exercises

Here is the whole laboratory: all five tests on the whole gallery. Use it to check your answers to the exercises, and to see which test is the most economical for each series.

Explore The convergence-test laboratory

Try this. Choose 1/(nlog⁡n)1/(n\log n) and run every test on it, then do the same for 1/(n(log⁡n)2)1/(n(\log n)^2). Finally pick a series from the top of the menu and decide which test is quickest.

∑n=2∞vn,vn=1nlog⁡n\sum_{n=2}^{\infty} v_n,\quad v_n = \frac{1}{n\log n}
kpartial sums
  • s2k+1−1s_{2^{k+1}-1}, the original series up to n=2k+1−1n = 2^{k+1}-1
  • ∑j≤k2jϕ(2j)\sum_{j \le k} 2^j\phi(2^j), the condensed series
Test
At k=11k = 11 (that is, n=4095n = 4095 terms of the original): original 2.9131, condensed 4.3568. 11 condensed terms do the work of about four thousand. Diverges. The condensed series has terms 2kϕ(2k)=2k2k klog⁡2=1klog⁡22^k\phi(2^k) = \frac{2^k}{2^k\, k\log 2} = \frac{1}{k\log 2}, which diverges; so the original series diverges too. The condensed series is a multiple of the harmonic series.
What to notice

For the two logarithmic series, comparison with powers of nn and the root and ratio tests are all silent; the integral and condensation tests decide them, in opposite ways, and about a dozen condensed terms already show the trend that four thousand ordinary terms barely reveal. For n2/2nn^2/2^n or 1/n!1/n! the ratio test is the fastest; for the interleaved series only the root test or a comparison works.

Exercise ●●○ Hardy: Examples LXXII, 1

Let a≥2a \ge 2 be an integer. Show that, for positive decreasing ϕ\phi, ∑ϕ(n)\sum\phi(n) converges or diverges with ∑anϕ(an)\sum a^n\phi(a^n).

Hint
Use blocks ak≤n<ak+1a^k \le n < a^{k+1}, which contain ak+1−ak=(a−1)aka^{k+1} - a^k = (a-1)a^k terms.

Solution

Upper bound. The block ak≤n<ak+1a^k \le n < a^{k+1} has (a−1)ak(a-1)a^k terms, each at most ϕ(ak)\phi(a^k), so its sum is at most (a−1) akϕ(ak)(a-1)\,a^k\phi(a^k). Summing, ∑n<aK+1ϕ(n)≤(a−1)∑k≤Kakϕ(ak)\sum_{n < a^{K+1}} \phi(n) \le (a-1)\sum_{k\le K} a^k\phi(a^k): convergence of the condensed series gives convergence.

Lower bound. The block ak<n≤ak+1a^k < n \le a^{k+1} has (a−1)ak(a-1)a^k terms, each at least ϕ(ak+1)\phi(a^{k+1}), so its sum is at least (a−1)akϕ(ak+1)=a−1a ak+1ϕ(ak+1)(a-1)a^k\phi(a^{k+1}) = \dfrac{a-1}{a}\, a^{k+1}\phi(a^{k+1}). Summing shows that divergence of the condensed series gives divergence. The constants a−1a - 1 and (a−1)/a(a-1)/a do not affect convergence.

Exercise ●●○ Hardy: Examples LXXII, 2

Show that if ∑2nϕ(2n)\sum 2^n\phi(2^n) converges then 2nϕ(2n)→02^n\phi(2^n) \to 0. Deduce Abel’s theorem: for positive decreasing ϕ\phi with ∑ϕ(n)\sum\phi(n) convergent, nϕ(n)→0n\phi(n) \to 0.

Hint
For 2k≤n<2k+12^k \le n < 2^{k+1}, compare nϕ(n)n\phi(n) with 2k+1ϕ(2k)2^{k+1}\phi(2^k).

Solution

The terms of a convergent series tend to 00, so ck=2kϕ(2k)→0c_k = 2^k\phi(2^k) \to 0.

Now let ∑ϕ(n)\sum\phi(n) converge. By the condensation test ∑ck\sum c_k converges, so ck→0c_k \to 0. For 2k≤n<2k+12^k \le n < 2^{k+1}, since ϕ\phi decreases, 0≤nϕ(n)≤2k+1ϕ(2k)=2ck0 \le n\phi(n) \le 2^{k+1}\phi(2^k) = 2c_k. As n→∞n \to \infty, the corresponding k→∞k \to \infty, so 2ck→02c_k \to 0 and nϕ(n)→0n\phi(n) \to 0.

Exercise Powers of a logarithm ●●○

Assuming the properties of log⁡\log from Chapter IX, show that ∑n≥21n(log⁡n)p\sum_{n\ge2} \dfrac{1}{n(\log n)^p} converges if p>1p > 1 and diverges if p≤1p \le 1.

Hint
Condense: what is 2kϕ(2k)2^k\phi(2^k) when ϕ(n)=1/(n(log⁡n)p)\phi(n) = 1/(n(\log n)^p)?

Solution

For p>0p > 0, ϕ\phi is positive and decreasing on n≥2n \ge 2. The condensed terms (from k=1k = 1) are

2k 12k(klog⁡2)p=1(log⁡2)p⋅1kp,2^k\,\frac{1}{2^k (k\log 2)^p} = \frac{1}{(\log 2)^p}\cdot\frac{1}{k^p},

a constant multiple of ∑k−p\sum k^{-p}, which converges exactly when p>1p > 1. For p≤0p \le 0 we have (log⁡n)p≤1(\log n)^p \le 1 once log⁡n≥1\log n \ge 1 (that is, n≥3n \ge 3), so the terms are at least 1/n1/n and the series diverges by comparison with ∑1/n\sum 1/n. Condensation has turned log⁡n\log n into kk: one level of the “scale of infinity” has been peeled off.

Exercise Condensing ∑1/n2\sum 1/n^2 by hand ●○○

Use the condensation inequality to show that ∑n≥11/n2≤2\sum_{n\ge1} 1/n^2 \le 2, and use the base-22 lower bound to show it is at least 1+12=1.51 + \tfrac12 = 1.5.

Solution

Upper. ∑ϕ(n)≤∑k≥02kϕ(2k)=∑2k4−k=∑2−k=2\sum \phi(n) \le \sum_{k\ge0} 2^k\phi(2^k) = \sum 2^k 4^{-k} = \sum 2^{-k} = 2.

Lower. ϕ(1)=1\phi(1) = 1, and ϕ(2)+ϕ(3)+⋯≥12∑k≥12kϕ(2k)=12∑k≥12−k=12\phi(2) + \phi(3) + \cdots \ge \tfrac12\sum_{k\ge1} 2^k\phi(2^k) = \tfrac12\sum_{k \ge 1} 2^{-k} = \tfrac12. So the sum is at least 1.51.5. The true value π2/6≈1.645\pi^2/6 \approx 1.645 lies between. The upper bound is the same as the integral test’s; the lower bound is better than its 11.

Check yourself

Check yourself Choose one

What is the condensed series of ∑n−s\sum n^{-s}?

Why

2nϕ(2n)=2n(2n)−s=2n(1−s)=(21−s)n2^n\phi(2^n) = 2^n (2^n)^{-s} = 2^{n(1-s)} = (2^{1-s})^n, a geometric series with ratio 21−s2^{1-s}. Forgetting the factor 2n2^n (the first option) would give a series that converges for every s>0s > 0, which is wrong. The last option evaluates ϕ\phi at nn instead of at 2n2^n.

Check yourself Enter a number

For ϕ(n)=1/n2\phi(n) = 1/n^2, what is the condensed term 2kϕ(2k)2^k\phi(2^k) at k=5k = 5?

Why

25/(25)2=1/25=1/32=0.031252^5/(2^5)^2 = 1/2^5 = 1/32 = 0.03125. It stands for the block 32≤n≤6332 \le n \le 63, whose actual sum is about 0.01590.0159, less than the condensed term, as the upper bound says.

Check yourself True or false?

The condensation test may be applied to ∑2+(−1)nn2\sum \dfrac{2 + (-1)^n}{n^2} as it stands.

Why

False: the terms 11,34,19,316,…\tfrac{1}{1}, \tfrac{3}{4}, \tfrac19, \tfrac{3}{16}, \dots do not decrease, so a single term ϕ(2k)\phi(2^k) cannot stand for its block. (Here ϕ(2k)=3/4k\phi(2^k) = 3/4^k happens to pick out the larger values.) The series does converge, since its terms are at most 3/n23/n^2; comparison is the right tool.

Check yourself True or false?

The condensed series of ∑1/n\sum 1/n is 1+1+1+⋯1 + 1 + 1 + \cdots.

Why

True: 2k⋅2−k=12^k \cdot 2^{-k} = 1. This is Hardy’s proof in §77 that the harmonic series diverges: each block 12k+1+⋯+12k+1\tfrac{1}{2^k+1} + \cdots + \tfrac{1}{2^{k+1}} is at least 12\tfrac12.

Hardy’s language

Summary

Summary
  • For positive decreasing ϕ\phi, ∑ϕ(n)\sum \phi(n) and ∑2nϕ(2n)\sum 2^n\phi(2^n) converge or diverge together.
  • Proof: each block 2k≤n<2k+12^k \le n < 2^{k+1} lies between 2kϕ(2k+1)2^k\phi(2^{k+1}) and 2kϕ(2k)2^k\phi(2^k).
  • Condensation turns n−sn^{-s} into a geometric series and 1/(n(log⁡n)p)1/(n(\log n)^p) into ∑k−p\sum k^{-p}.
  • Without the decrease the test means nothing; use comparison instead.