# Math for Non-Geeks/ Cauchy condensation test

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 monotonically 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}$ (monotonically 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 monotonically 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 monotonically 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 monotonically 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

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}}$
Math for Non-Geeks: Template:Aufgabe