The Cauchy Condensation Test

For my first post, I decided to share an interesting little theorem I came across (and decided to prove) called the Cauchy Condensation Test. It provides a criterion for deciding whether a certain series (with positive decreasing terms) converges. It is useful in that the p-series test falls out somewhat naturally from it.

Theorem 1 (Cauchy Condensation Test). Let $\sum_{i=1}^\infty a_k$ be a series of positive terms with $a_{k+1} \leq a_k$. Then $\sum a_k$ converges if and only if $\sum_{k=0}^\infty 2^k a_{2^k}$ converges.

Proof. Let $A_n = \sum_{k=1}^n a_k$. Suppose first that $(A_n)$ converges. We will show that $\sum_{k=0}^\infty 2^k a_{2^k}$ converges.

For this we consider the sum $\sum_{k=1}^\infty s_k = \sum_{k=1}^\infty 2^{k-1} a_{2^k}$. The idea here is to group the $a_k$ terms so that each $s_k$ is bounded by a sum of $a_k$s (with each $a_k$ being used only once). Since the $a_k$ terms are decreasing, it follows that $2^{k-1}a_{2^k} \leq a_{2^{k-1}+1}+\cdots + a_{2^k}.$ Summing from $1$ to $n$ then gives:

$\sum_{k=1}^n 2^{k-1} a_{2^k} \leq \sum_{k=1}^n a_{2^{k-1}+1}+\cdots + a_{2^k} \leq A_{2^n} < \lim_{n\to \infty} A_n=C$, for some constant $C$. As $n\to \infty$, the sum stays bounded, and so must converge (since the sequence of partial sums is then monotone increasing and bounded) to some value $S$. It is then easy to see that $\sum_{k=0}^\infty 2^k a_{2^k}$ converges to $2S+a_1$. A similar sort of idea works for the reverse direction, except this time we can use the sum directly. Consider $A_{2^{k}-1}=a_1+(a_2+a_3)+\cdots+(a_{2^{k-1}}+\cdots+a_{2^k-1}).$ Again since the terms are decreasing, we can bound each term by the first term in its group (denoted by parenthesis): $RHS \leq a_1 +2a_2 + \cdots + (2^{k}-1)a_{2^{k}-1} \leq \sum_{k=0}^{k} 2^k a_{2^k} \leq \sum_{k=0}^{\infty} 2^k a_{2^k} = C$, for some constant $C$. Thus we have $A_{2^k-1} \leq C$, and letting $k\to \infty$ shows that the series converges.

Note: The "shifting" idea behind this proof can also be used to prove the famous Integral Test for series, which says that if $f$ is continuous, nonnegative, and monotone decreasing on $[1,\infty)$, then $\sum_{i=1}^\infty f(i)$ and $\int_1^\infty f(x)dx$ converge or diverge together.

Now for an application of the Cauchy Condensation Test, we show how it leads to an easy proof of the $p$-series test. The $p$-series test says that $\sum_{k=1}^\infty \frac{1}{k^p}$ converges if $p > 1$ and diverges to $\infty$ if $p\leq 1$.

We can thus turn to the series $\sum_{k=1}^\infty 2^k \frac{1}{2^{kp}}=\sum_{k=1}^\infty {2^{(1-p)}}^k$. Seemingly miraculously, we have gone from considering a $p$-series to a much simpler geometric series! We can easily see that this series converges if $p>1$ and diverges to $\infty$ if $p\leq 1$. By the condensation test, the series $\sum_{k=1}^\infty \frac{1}{k^p}$ must do the same.