## Cauchy Condensation Test

The Cauchy Condensation Test states that for a decreasing sequence $\{a_n\}$ where $a_n\geq 0$ for all $n\in\mathbb{N}$ then $\sum\limits_{n=0}^{\infty}a_n$ converges if and only if $\sum\limits_{n=0}^{\infty}2^na_{2^n}$ converges.

Proof: In the forward direction, let us assume that $\sum\limits_{n=1}^{\infty}a_n$ converges. This means that the sequence of partial sums, $\{S_N=\sum\limits_{n=1}^{N}a_n\}$ converge. Define $T_N=\sum\limits_{n=1}^{N}2^na_{2^n}$. We wish to show that the sequence $\{T_n\}$ converges.

$T_N=a_1+2a_2+4a_4+\dots+2^Na_{2^N}$

$=(a_1+a_2)+(a_2+a_4)+\dots+2^Na_{2^N}$

Since $a_n\geq a_m$ for every $n>m\in\mathbb{N}$ it follows that $a_1+a_2\leq 2a_1$ and that $a_2+a_4\leq 2a_2$. We may make similar arguments for the rest of the partial sum, resulting with

$T_N\leq 2a_1+2a_2+\dots+2a_{2^N}$

$=2(a_1+a_2+\dots+a_{2^N})=2S_{2^N}$

Thus $T_N\leq 2S_N$ for every $N\in\mathbb{N}$. We are given that $\{S_N\}$ converges by our assumption and so any subsequence, specifically $\{S_{2^N}\}$, also converges, and so $\{2S_N\}$ also converges. So we have that $\{T_N\}$ is bounded above by a convergent sequence. Furthermore we know $\{T_n\}$ is increasing since $a_n\geq 0$ for every $n\in\mathbb{N}$. Thus we have a bounded, monotonic sequence and so it follows that $\{T_N\}$ converges. This implies that $\sum\limits_{n=0}^{\infty}2^na_{2^n}$ converges.

Now for the reverse direction. Assume that $\sum\limits_{n=0}^{\infty}2^na_{2^n}$ converges. Consider the partial sum

$S_{2^{N+1}-1}=a_0+a_1+a_2+a_3+\dots+a_{2^{N+1}-1}$

Since $a_m\geq a_n$ for  all $m,n\in\mathbb{N}$ it follows that $a_2+a_3\leq 2a_2$ and $a_4+a_5+a_6+a_7\leq 4a_4$. Continuing in this manner results in the following inequality:

$S_{2^{N+1}-1}\leq a_0+a_1+2a_2+4a_4+\dots+2^Na_{2^N}$

$=a_0+T_N$

I claim that this implies that $\{S_n\}$ converges. Let $m\in\mathbb{N}$ and consider $S_m$. Since $a_n\geq 0$ for all $n$ there is some $N\in\mathbb{N}$ such that $S_m\leq S_{2^{N+1}-1}\leq a_0+T_N$. Thus the sequence $\{S_n\}$ is bounded and increasing. Every bounded monotonic sequence converges and so we may conclude that $\{S_n\}$ converges, thus, $\sum\limits_{n=0}^{\infty}a_n$ converges.

$\Box$

Reflection: This was another one of those problems where I was over-thinking. The proof really falls straight from definition, with some algebra tweaking along the way. The main thing I was worried about with this proof was the reverse direction, since I was able to bound a subsequence and not the whole sequence. The reason this wasn’t a problem in this case is because our $a_n$ are all greater than or equal to $0$. So, I was able to bound every term in the  sequence by my previously bounded terms in the subsequence. After stating that I felt a lot more comfortable concluding that the sequence converged.

This is a really nice theorem to know, especially since it’s and if and only if. Also, it’s given me another weapon in my arsenal with which to test for convergence.