Cauchy condensation test – Serlo

In this chapter, we present the Cauchy condensation test (named by Augustin Louis Cauchy). It allows us to only check the condensed series $\sum _{k=0}^{\infty }2^{k}a_{2^{k}}$ for convergence , which contains way less elements than the original series $\sum _{k=1}^{\infty }a_{k}$ . More precisely, in case the series elements $a_{k}$ are non-negative and decreasing, we know that the original series $\sum _{k=1}^{\infty }a_{k}$ converges if and only if the condensed series $\sum _{k=0}^{\infty }2^{k}a_{2^{k}}$ converges. The derivation will involve a direct comparison to a divergent harmonic series $\sum _{k=1}^{\infty }{\frac {1}{k}}$ and convergence to a convergent generalized harmonic series $\sum _{k=1}^{\infty }{\frac {1}{k^{\alpha }}}$ für $\alpha >1$.

Repetition and derivation of the criterion

For proving divergence of the harmonic series $\sum _{k=1}^{\infty }{\tfrac {1}{k}}$ , we used a lower bound for each $2^{n}$-th partial sum $\sum _{k=1}^{2^{n}}{\tfrac {1}{k}}$ :

${\begin{aligned}\sum _{k=1}^{2^{n}}{\frac {1}{k}}&=1+{\color {Orange}{\frac {1}{2}}}+{\color {OliveGreen}\left({\frac {1}{3}}+{\frac {1}{4}}\right)}+{\color {Blue}\left({\frac {1}{5}}+{\frac {1}{6}}+{\frac {1}{7}}+{\frac {1}{8}}\right)}+\ldots +{\color {CadetBlue}\left({\frac {1}{2^{n-1}+1}}+\ldots +{\frac {1}{2^{n}-1}}+{\frac {1}{2^{n}}}\right)}\\[0.5em]&\left\downarrow \ {\text{bound the summands: }}{\color {OliveGreen}{\frac {1}{3}}\geq {\frac {1}{4}}}\land {\color {Blue}{\frac {1}{5}}\geq {\frac {1}{6}}\geq {\frac {1}{7}}\geq {\frac {1}{8}}}\land \ldots \right.\\[0.5em]&\geq 1+{\color {Orange}{\frac {1}{2}}}+{\color {OliveGreen}\left({\frac {1}{4}}+{\frac {1}{4}}\right)}+{\color {Blue}\left({\frac {1}{8}}+{\frac {1}{8}}+{\frac {1}{8}}+{\frac {1}{8}}\right)}+\ldots +{\color {CadetBlue}\left({\frac {1}{2^{n}}}+\ldots +{\frac {1}{2^{n}}}+{\frac {1}{2^{n}}}\right)}\\[0.5em]&\left\downarrow \ {\text{gather the summands}}\right.\\[0.5em]&=1+{\color {Orange}{\frac {1}{2}}}+{\color {OliveGreen}2\cdot {\frac {1}{4}}}+{\color {Blue}4\cdot {\frac {1}{8}}}+\ldots +{\color {CadetBlue}2^{n-1}\cdot {\frac {1}{2^{n}}}}\\[0.5em]&=1+\underbrace {{\color {Orange}{\frac {1}{2}}}+{\color {OliveGreen}{\frac {1}{2}}}+{\color {Blue}{\frac {1}{2}}}+\ldots +{\color {CadetBlue}{\frac {1}{2}}}} _{n{\text{ summands}}}=1+{\frac {n}{2}}\end{aligned}}$

How can we generalize this concept to a general series $\sum _{k=1}^{\infty }a_{k}$ ? In order to make the same estimation steps, the series must have some properties identical to the harmonic series:

• The series elements $a_{k}$ have to be non-negative.
• The sequence of elements $a_{k}$ has to be monotonously decreasing.

If $\sum _{k=1}^{\infty }a_{k}$ is a series with non-negative elements fulfilling $a_{k}\geq a_{k+1}$ for all $k\in \mathbb {N}$. Then

${\begin{aligned}\sum _{k=1}^{2^{n}}a_{k}&=a_{1}+{\color {Orange}a_{2}}+{\color {OliveGreen}\left(a_{3}+a_{4}\right)}+{\color {Blue}\left(a_{5}+a_{6}+a_{7}+a_{8}\right)}+\ldots +{\color {CadetBlue}\left(a_{2^{n-1}+1}+\ldots +a_{2^{n}-1}+a_{2^{n}}\right)}\\[0.5em]&\left\downarrow \ {\text{bound the summands: }}{\color {OliveGreen}a_{3}\geq a_{4}}\land {\color {Blue}a_{5}\geq a_{6}\geq a_{7}\geq a_{8}}\land \ldots \right.\\[0.5em]&\geq a_{1}+{\color {Orange}a_{2}}+{\color {OliveGreen}\left(a_{4}+a_{4}\right)}+{\color {Blue}\left(a_{8}+a_{8}+a_{8}+a_{8}\right)}+\ldots +{\color {CadetBlue}\left(a_{2^{n}}+\ldots +a_{2^{n}}+a_{2^{n}}\right)}\\[0.5em]&\left\downarrow \ {\text{gather the summands}}\right.\\[0.5em]&=a_{1}+{\color {Orange}a_{2}}+{\color {OliveGreen}2\cdot a_{4}}+{\color {Blue}4\cdot a_{8}}+\ldots +{\color {CadetBlue}2^{n-1}\cdot a_{2^{n}}}\\[0.5em]&\left\downarrow \ {\text{adjust index and pre-factor}}\right.\\[0.5em]&\geq {\frac {1}{2}}a_{1}+{\color {Orange}{\frac {1}{2}}2a_{2}}+{\color {OliveGreen}{\frac {1}{2}}4a_{4}}+{\color {Blue}{\frac {1}{2}}8a_{8}}+\ldots +{\color {CadetBlue}{\frac {1}{2}}2^{n}a_{2^{n}}}\\[0.5em]&\left\downarrow \ {\frac {1}{2}}{\text{ factor out}}\right.\\[0.5em]&={\frac {1}{2}}(a_{1}+{\color {Orange}2a_{2}}+{\color {OliveGreen}4a_{4}}+{\color {Blue}8a_{8}}+\ldots +{\color {CadetBlue}2^{n}a_{2^{n}}})\\[0.5em]&={\frac {1}{2}}\sum _{k=0}^{n}2^{k}a_{2^{k}}\end{aligned}}$

So we estimated $\sum _{k=1}^{2^{n}}a_{k}$ from below by ${\frac {1}{2}}\sum _{k=0}^{n}2^{k}a_{2^{k}}$ . That means, that if the condensed series $\sum _{k=0}^{\infty }2^{k}a_{2^{k}}$ diverges and hence, ${\frac {1}{2}}\sum _{k=0}^{\infty }2^{k}a_{2^{k}}$ as well, then the series $\sum _{k=1}^{\infty }a_{k}$ also diverges by direct comparison. Conversely (by contraposition), if $\sum _{k=1}^{\infty }a_{k}$ converges, then $\sum _{k=0}^{\infty }2^{k}a_{2^{k}}$ converges, as well.

For the proof that the generalized harmonic series $\sum _{k=1}^{\infty }{\tfrac {1}{k^{\alpha }}}$ with $\alpha >1$ converges, we compared the $n$-th partial sum $\sum _{k=1}^{n}{\tfrac {1}{k^{\alpha }}}$ for $n\leq 2^{m+1}-1$ to a convergent geometric series $\sum _{i=0}^{m}\left({\tfrac {1}{2^{\alpha -1}}}\right)^{i}$ . The bounding worked as follows:

${\begin{aligned}\sum _{k=1}^{n}{\frac {1}{k^{\alpha }}}&\leq \sum _{k=1}^{2^{m+1}-1}{\frac {1}{k^{\alpha }}}\\[0.5em]&=1+{\color {Orange}{\frac {1}{2^{\alpha }}}+{\frac {1}{3^{\alpha }}}}+{\color {OliveGreen}\left({\frac {1}{4^{\alpha }}}+{\frac {1}{5^{\alpha }}}+{\frac {1}{6^{\alpha }}}+{\frac {1}{7^{\alpha }}}\right)}+\ldots +{\color {Blue}\underbrace {\left({\frac {1}{(2^{m})^{\alpha }}}+\ldots +{\frac {1}{(2^{m+1}-1)^{\alpha }}}\right)} _{2^{m}{\text{ summands}}}}\\[0.5em]&\left\downarrow \ {\color {Orange}{\frac {1}{3^{\alpha }}}\leq {\frac {1}{2^{\alpha }}}}\land {\color {OliveGreen}{\frac {1}{7^{\alpha }}}\leq {\frac {1}{6^{\alpha }}}\leq {\frac {1}{5^{\alpha }}}\leq {\frac {1}{4^{\alpha }}}}\land \ldots \land {\color {Blue}{\frac {1}{(2^{m+1}-1)^{\alpha }}}\leq \cdots \leq {\frac {1}{(2^{m})^{\alpha }}}}\quad ({\text{da }}\alpha >1)\right.\\[0.5em]&\leq 1+{\color {Orange}{\frac {1}{2^{\alpha }}}+{\frac {1}{2^{\alpha }}}}+{\color {OliveGreen}\left({\frac {1}{4^{\alpha }}}+{\frac {1}{4^{\alpha }}}+{\frac {1}{4^{\alpha }}}+{\frac {1}{4^{\alpha }}}\right)}+\ldots +{\color {Blue}\underbrace {\left({\frac {1}{(2^{m})^{\alpha }}}+\ldots +{\frac {1}{(2^{m})^{\alpha }}}\right)} _{2^{m}{\text{ summands}}}}\\[0.5em]&=1+{\color {Orange}\left(2\cdot {\frac {1}{2^{\alpha }}}\right)}+{\color {OliveGreen}4\cdot {\frac {1}{4^{\alpha }}}}+\cdots +{\color {Blue}2^{m}\cdot {\frac {1}{(2^{m})^{\alpha }}}}\\[0.5em]&=1+{\color {Orange}{\frac {1}{2^{\alpha -1}}}}+{\color {OliveGreen}{\frac {1}{4^{\alpha -1}}}}+\cdots +{\color {Blue}{\frac {1}{(2^{m})^{\alpha -1}}}}\\[0.5em]&={\frac {1}{(2^{\alpha -1})^{0}}}+{\color {Orange}{\frac {1}{(2^{\alpha -1})^{1}}}}+{\color {OliveGreen}{\frac {1}{(2^{\alpha -1})^{2}}}}+\cdots +{\color {Blue}{\frac {1}{(2^{\alpha -1})^{m}}}}\\[0.5em]&=\sum _{i=0}^{m}{\frac {1}{(2^{\alpha -1})^{i}}}\leq \sum _{i=0}^{\infty }\left({\frac {1}{2^{\alpha -1}}}\right)^{i}={\frac {1}{1-2^{1-\alpha }}}<\infty \end{aligned}}$

We try to do the same for a general series $\sum _{k=1}^{\infty }a_{k}$ with

• non-negative elements $a_{k}$
• and $a_{k+1}\leq a_{k}$ for all $k\in \mathbb {N}$ (monotonously decreasing sequence of elements)

Let $n\leq 2^{m+1}-1$. then,

${\begin{aligned}\sum _{k=1}^{n}a_{k}&\leq \sum _{k=1}^{2^{m+1}-1}a_{k}\\[0.5em]&=a_{1}+{\color {Orange}a_{2}+a_{3}}+{\color {OliveGreen}\left(a_{4}+a_{5}+a_{6}+a_{7}\right)}+\ldots +{\color {Blue}\underbrace {\left(a_{2^{m}}+\ldots +a_{2^{m+1}-1}\right)} _{2^{m}{\text{ summands}}}}\\[0.5em]&\left\downarrow \ {\color {Orange}a_{3}\leq a_{2}}\land {\color {OliveGreen}a_{7}\leq a_{6}\leq a_{5}\leq a_{4}}\land \ldots \land {\color {Blue}a_{2^{m+1}-1}\leq \cdots \leq a_{2^{m}}}\right.\\[0.5em]&\leq a_{1}+{\color {Orange}a_{2}+a_{2}}+{\color {OliveGreen}\left(a_{4}+a_{4}+a_{4}+a_{4}\right)}+\ldots +{\color {Blue}\underbrace {\left(a_{2^{m}}+\ldots +a_{2^{m}}\right)} _{2^{m}{\text{ summands}}}}\\[0.5em]&=a_{1}+{\color {Orange}2\cdot a_{2}}+{\color {OliveGreen}4\cdot a_{4}}+\cdots +{\color {Blue}2^{m}\cdot a_{2^{m}}}\\[0.5em]&=\sum _{k=0}^{m}2^{k}a_{2^{k}}\end{aligned}}$

So we can also bound $\sum _{k=1}^{n}a_{k}$ from above by $\sum _{k=0}^{n}2^{k}a_{2^{k}}$ . Direct comparison can again be applied and leads us to the conclusion: If the condensed series $\sum _{k=0}^{\infty }2^{k}a_{2^{k}}$ converges, the the original series $\sum _{k=1}^{\infty }a_{k}$ also converges.

So if elements are non-negative and monotonously decreasing, we have an equivalence between the convergence of the series $\sum _{k=1}^{n}a_{k}$ and the condensed series $\sum _{k=0}^{\infty }2^{k}a_{2^{k}}$ . This result is called Cauchy condensation test. It can be very useful, to remove logarithms out of a series. For instance, if $a_{k}=\ln(ln(k))...$. Then, for the condensed series $a_{2^{k}}=\ln(k\cdot \ln(2))...$. So condensation can remove double logarithms.

Now, let us formulate these findings in a mathematical language, i.e. a theorem with a proof:

Theorem (Cauchy condensation criterion)

Let $(a_{n})_{n\in \mathbb {N} }$ be a non-negative and monotonously decreasing sequence. Then, the series $\sum _{k=1}^{\infty }a_{k}$ converges if and only if the condensed series $\sum _{k=0}^{\infty }2^{k}a_{2^{k}}$ converges.

Proof (Cauchy condensation criterion)

Proof step: "$\Rightarrow$"

For the sequence of partial sums $(S_{2^{n}})$ there is

${\begin{aligned}\sum _{k=1}^{2^{n}}a_{k}&=a_{1}+{\color {Orange}a_{2}}+{\color {OliveGreen}\left(a_{3}+a_{4}\right)}+{\color {Blue}\left(a_{5}+a_{6}+a_{7}+a_{8}\right)}+\ldots +{\color {CadetBlue}\left(a_{2^{n-1}+1}+\ldots +a_{2^{n}-1}+a_{2^{n}}\right)}\\[0.5em]&\left\downarrow \ {\text{bound the summands: }}{\color {OliveGreen}a_{3}\geq a_{4}}\land {\color {Blue}a_{5}\geq a_{6}\geq a_{7}\geq a_{8}}\land \ldots \right.\\[0.5em]&\geq a_{1}+{\color {Orange}a_{2}}+{\color {OliveGreen}\left(a_{4}+a_{4}\right)}+{\color {Blue}\left(a_{8}+a_{8}+a_{8}+a_{8}\right)}+\ldots +{\color {CadetBlue}\left(a_{2^{n}}+\ldots +a_{2^{n}}+a_{2^{n}}\right)}\\[0.5em]&\left\downarrow \ {\text{gather the summands}}\right.\\[0.5em]&=a_{1}+{\color {Orange}a_{2}}+{\color {OliveGreen}2\cdot a_{4}}+{\color {Blue}4\cdot a_{8}}+\ldots +{\color {CadetBlue}2^{n-1}\cdot a_{2^{n}}}\\[0.5em]&\left\downarrow \ {\text{adjust index and pre-factor}}\right.\\[0.5em]&\geq {\frac {1}{2}}a_{1}+{\color {Orange}{\frac {1}{2}}2a_{2}}+{\color {OliveGreen}{\frac {1}{2}}4a_{4}}+{\color {Blue}{\frac {1}{2}}8a_{8}}+\ldots +{\color {CadetBlue}{\frac {1}{2}}2^{n}a_{2^{n}}}\\[0.5em]&\left\downarrow \ {\frac {1}{2}}{\text{ factorize}}\right.\\[0.5em]&={\frac {1}{2}}(a_{1}+{\color {Orange}2a_{2}}+{\color {OliveGreen}4a_{4}}+{\color {Blue}8a_{8}}+\ldots +{\color {CadetBlue}2^{n}a_{2^{n}}})\\[0.5em]&={\frac {1}{2}}\sum _{k=0}^{n}2^{k}a_{2^{k}}\end{aligned}}$

If the sequence / series $(S_{n})_{n\in \mathbb {N} }=\sum _{k=1}^{\infty }a_{k}$ converges, then also the subsequence $(S_{2^{n}})_{n\in \mathbb {N} }$ will converge. The above bounding implies that then also ${\tfrac {1}{2}}\sum _{k=0}^{\infty }2^{k}a_{2^{k}}$ converges. Multiplying by ${\tfrac {1}{2}}$, we also get convergence of the condensed series $\sum _{k=0}^{\infty }2^{k}a_{2^{k}}$.

Proof step: "$\Leftarrow$"

For the $n$-th partial sum $\sum _{k=1}^{\infty }a_{k}$ and for $n\leq 2^{m+1}-1$, there is:

${\begin{aligned}\sum _{k=1}^{n}a_{k}&\leq \sum _{k=1}^{2^{m+1}-1}a_{k}\\[0.5em]&=a_{1}+{\color {Orange}a_{2}+a_{3}}+{\color {OliveGreen}\left(a_{4}+a_{5}+a_{6}+a_{7}\right)}+\ldots +{\color {Blue}\underbrace {\left(a_{2^{m}}+\ldots +a_{2^{m+1}-1}\right)} _{2^{m}{\text{ summands}}}}\\[0.5em]&\left\downarrow \ {\color {Orange}a_{3}\leq a_{2}}\land {\color {OliveGreen}a_{7}\leq a_{6}\leq a_{5}\leq a_{4}}\land \ldots \land {\color {Blue}a_{2^{m+1}-1}\leq \cdots \leq a_{2^{m}}}\right.\\[0.5em]&\leq a_{1}+{\color {Orange}a_{2}+a_{2}}+{\color {OliveGreen}\left(a_{4}+a_{4}+a_{4}+a_{4}\right)}+\ldots +{\color {Blue}\underbrace {\left(a_{2^{m}}+\ldots +a_{2^{m}}\right)} _{2^{m}{\text{ summands}}}}\\[0.5em]&=a_{1}+{\color {Orange}2\cdot a_{2}}+{\color {OliveGreen}4\cdot a_{4}}+\cdots +{\color {Blue}2^{m}\cdot a_{2^{m}}}\\[0.5em]&=\sum _{k=0}^{m}2^{k}a_{2^{k}}\end{aligned}}$

now, if the series $\sum _{k=0}^{\infty }2^{k}a_{2^{k}}$ converges, then by the above estimate, $\sum _{k=1}^{\infty }a_{k}$ must be bounded and hence convergent.

Hint

Analogously, one can show that a non-positive series with elements monotonously increasing (e.g. up to 0) converges, if and only if the condensed series converges.

Warning

The condensation test is NOT treated in all calculus courses. The main reason for this is that there are not too many applications, where it is useful. Basically only for eliminating logarithms. Please, only quote this test in your exercise solution, if it was treated somewhere in the lecture! Otherwise, you may reduce the condensation test to a direct comparison test, by making the same estimates as in the proof above.

Applications

Application of the condensation test (Video in German:YouTube-Video vom YouTube-Channel Quatematik)

Example (Cauchy condensation test and the zeta function)

As seen above, the Cauchy condensation test can be used to prove the convergence / divergence for the generalized harmonic series $\sum \limits _{k=1}^{\infty }{\frac {1}{k^{\alpha }}}$ for $\alpha >0$. This series converges if and only if the condensed series converges:

${\begin{aligned}\sum \limits _{k=0}^{\infty }2^{k}{\frac {1}{(2^{k})^{\alpha }}}&=\sum \limits _{k=0}^{\infty }{\frac {1}{(2^{k})^{\alpha -1}}}\\&=\sum \limits _{k=0}^{\infty }{\frac {1}{(2^{\alpha -1})^{k}}}\\&=\sum \limits _{k=0}^{\infty }\left({\frac {1}{2^{\alpha -1}}}\right)^{k}\end{aligned}}$

This is just a geometric series $\sum \limits _{k=0}^{\infty }q^{k}$ with $q={\frac {1}{2^{\alpha -1}}}$. It converges if and only if

${\begin{aligned}{\frac {1}{2^{\alpha -1}}}<1&\Leftrightarrow 2^{\alpha -1}>1\\&\Leftrightarrow \alpha -1>0\\&\Leftrightarrow \alpha >1\end{aligned}}$

By the Cauchy condensation test, the generalized harmonic series $\sum \limits _{k=1}^{\infty }{\frac {1}{k^{\alpha }}}$ converges if and only if $\alpha >1$ . Especially, for $0<\alpha \leq 1$ , it diverges. Usually, in the convergent case $\alpha <0$, one defines the

Riemann zeta function as the limit of this generalized harmonic series $\mathrm {Z} (\alpha )=\sum \limits _{k=1}^{\infty }{\frac {1}{k^{\alpha }}}$.

You may just use in an exercise that this result is finite, without referring to the Cauchy condensation - or any other test especially, $\mathrm {Z} (2)=\sum \limits _{k=1}^{\infty }{\frac {1}{k^{2}}}={\tfrac {\pi ^{2}}{6}}$

Exercise (Removing logarithms)

Investigate for $\alpha >0$ whether the series $\sum \limits _{k=2}^{\infty }{\frac {1}{k(\ln(k))^{\alpha }}}$ converges.

Proof (Removing logarithms)

By means of the Cauchy condensation test, this series converges if and only if the following condensed series converges:

${\begin{aligned}\sum \limits _{k=1}^{\infty }2^{k}{\frac {1}{2^{k}(\ln(2^{k}))^{\alpha }}}&=\sum \limits _{k=1}^{\infty }{\frac {1}{\ln(2^{k})^{\alpha }}}\\&\ \left\downarrow \ \ln(x^{y})=y\ln(x)\right.\\&=\sum \limits _{k=1}^{\infty }{\frac {1}{(k\ln(2))^{\alpha }}}\\&=\sum \limits _{k=1}^{\infty }{\frac {1}{k^{\alpha }}}{\frac {1}{\ln(2)^{\alpha }}}\end{aligned}}$

This is just a generalized harmonic series with a constant pre-factor ${\frac {1}{\ln(2)^{\alpha }}}$. The example above shows that this series converges if and only if $\alpha >1$ and diverges if and only if $0<\alpha \leq 1$ .