Cauchy condensation test

In mathematics, the Cauchy condensation test, named after Augustin-Louis Cauchy, is a standard convergence test for infinite series. For a non-negative, non-increasing sequence $f(n)$ of real numbers, the series $\textstyle \sum _{{n=1}}^{{\infty }}f(n)$ converges if and only if the "condensed" series $\textstyle \sum _{{n=0}}^{{\infty }}2^{{n}}f(2^{{n}})$ converges. Moreover, if they converge, the sum of the condensed series is no more than twice as large as the sum of the original.

Estimate

The Cauchy condensation test follows from the stronger estimate

$0\ \leq \ \sum _{{n=1}}^{{\infty }}f(n)\ \leq \ \sum _{{n=0}}^{{\infty }}2^{{n}}f(2^{{n}})\ \leq \ 2\sum _{{n=1}}^{{\infty }}f(n)\ \leq \ +\infty$

which should be understood as an inequality of extended real numbers. The essential thrust of a proof follows, following the line of Oresme's proof of the divergence of the harmonic series.

To see the first inequality, the terms of the original series are rebracketed into runs whose lengths are powers of two, and then each run is bounded above by replacing each term by the largest term in that run: the first one, since the terms are non-increasing.

${\begin{array}{rcccccccl}\sum _{{n=1}}^{{\infty }}f(n)&=&f(1)&+&f(2)+f(3)&+&f(4)+f(5)+f(6)+f(7)&+&\cdots \\&=&f(1)&+&{\Big (}f(2)+f(3){\Big )}&+&{\Big (}f(4)+f(5)+f(6)+f(7){\Big )}&+&\cdots \\&\leq &f(1)&+&{\Big (}f(2)+f(2){\Big )}&+&{\Big (}f(4)+f(4)+f(4)+f(4){\Big )}&+&\cdots \\&=&f(1)&+&2f(2)&+&4f(4)&+&\cdots =\sum _{{n=0}}^{{\infty }}2^{{n}}f(2^{{n}})\end{array}}$

To see the second, the two series are again rebracketed into runs of power of two length, but "offset" as shown below, so that the run of $\textstyle 2\sum _{{n=1}}^{{\infty }}f(n)$ which begins with $\textstyle f(2^{{n}})$ lines up with the end of the run of $\textstyle \sum _{{n=0}}^{{\infty }}2^{{n}}f(2^{{n}})$ which ends with $\textstyle f(2^{{n}})$, so that the former stays always "ahead" of the latter.

${\begin{array}{rcl}\sum _{{n=0}}^{{\infty }}2^{{n}}f(2^{{n}})&=&f(1)+{\Big (}f(2)+f(2){\Big )}+{\Big (}f(4)+f(4)+f(4)+f(4){\Big )}+\cdots \\&=&{\Big (}f(1)+f(2){\Big )}+{\Big (}f(2)+f(4)+f(4)+f(4){\Big )}+\cdots \\&\leq &{\Big (}f(1)+f(1){\Big )}+{\Big (}f(2)+f(2)+f(3)+f(3){\Big )}+\cdots =2\sum _{{n=1}}^{{\infty }}f(n)\end{array}}$

Visualization of the above argument. Partial sums of the series $\textstyle \sum f(n)$, $\sum 2^{{n}}f(2^{{n}})$, and $2\sum f(n)$ are pictured.

Integral comparison

The "condensation" transformation $\textstyle f(n)\rightarrow 2^{{n}}f(2^{{n}})$ recalls the integral variable substitution $\textstyle x\rightarrow e^{{x}}$ yielding $\textstyle f(x)\,{\mathrm {d}}x\rightarrow e^{{x}}f(e^{{x}})\,{\mathrm {d}}x$.

Pursuing this idea, the integral test for convergence gives us that $\textstyle \sum _{{n=1}}^{{\infty }}f(n)$ converges if and only if $\textstyle \int _{{1}}^{{\infty }}f(x)\,{\mathrm {d}}x$ converges. The substitution $\textstyle x\rightarrow 2^{x}$ yields the integral $\textstyle \log 2\,\int _{{0}}^{{\infty }}2^{{x}}f(2^{{x}})\,{\mathrm {d}}x$ and another integral test brings us to the condensed series $\textstyle \sum _{{n=0}}^{{\infty }}2^{{n}}f(2^{{n}})$.

Examples

The test can be useful for series where n appears as in a denominator in f. For the most basic example of this sort, the harmonic series $\textstyle \sum _{{n=1}}^{{\infty }}1/n$ is transformed into the series $\textstyle \sum 1$, which clearly diverges.

As a more complex example, take

$f(n):=n^{{-a}}(\log n)^{{-b}}(\log \log n)^{{-c}}$.

Here the series definitely converges for a > 1, and diverges for a < 1. When a = 1, the condensation transformation gives the series

$\sum n^{{-b}}(\log n)^{{-c}}$.

The logarithms 'shift to the left'. So when a = 1, we have convergence for b > 1, divergence for b < 1. When b = 1 the value of c enters.

The condensation test, applied repeatedly, can be used to show that for any $k$, the generalized Bertrand series

${\displaystyle \sum _{n\geq N}{\frac {1}{n\cdot \log n\cdot \log ^{\circ 2}n\cdots \log ^{\circ (k-1)}n\cdot (\log ^{\circ k}n)^{\alpha }}},\ N=\lfloor \exp ^{\circ (k-1)}(1)\rfloor +1}$

converges for $\alpha >1$ and diverges for ${\displaystyle 0<\alpha \leq 1}$. Here, we have used the notation ${\displaystyle f^{\circ m}}$ for the mth iterate of a function $f$, so that ${\displaystyle f^{\circ m}:=f^{\circ (m-1)}\circ f}$ with ${\displaystyle f^{\circ 1}:=f}$. The lower limit of the sum $N$ was chosen so that all terms of the series are positive. Notably, this result provides examples of series that converge or diverge at an arbitrarily slow rate. For instance, when $k=2$ and $\alpha =1$, the sum exceeds 10 only after a googolplex terms yet diverges nevertheless.

Generalization

The following generalization is due to Schlömilch. Let u(n) be a strictly increasing sequence of positive integers such that

${\Delta u(n) \over \Delta u(n-1)}={u(n+1)-u(n) \over u(n)-u(n-1)}$

is bounded, where $\Delta u(n)$ is the forward difference of u. Then the series $\textstyle \sum _{{n=1}}^{{\infty }}f(n)$ converges if and only if^[1] the series

$\sum _{{n=0}}^{{\infty }}{\Delta u(n)}f(u(n))=\sum _{{n=0}}^{{\infty }}{\Big (}u(n+1)-u(n){\Big )}f(u(n))$

converges. Taking $\textstyle u(n)=2^{n}$ so that $\textstyle \Delta u(n)=2^{n}$, the Cauchy condensation test emerges as a special case.

References

1. http://people.brandeis.edu/~joyner/everytopic/LiflyandCauchyTalk.pdf

• Bonar, Khoury (2006). Real Infinite Series. Mathematical Association of America. ISBN 0-88385-745-6.

External links

• Cauchy condensation test proof