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.

Advertisements
This entry was posted in Analysis, Math, Sequence, Series. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s