Proving that Cauchy condensation test is true for $a_n$ any monotone sequence. I'm trying to show that then $\Sigma a_n$ converges iff $\Sigma 2^n a_{2^n}$ converges if $a_n$ is any monotone sequence. 
I am assuming I have to prove the cases: 


*

*$a_n$ is positive and increasing

*$a_n$ is negative and increasing

*$a_n$ is positive and decreasing 

*$a_n$ is negative and decreasing


Here is what I have worked out from some of the comments below:

Assume $a_n$ is an increasing sequence. If $a_n$ is positive, then $\lim a_n \neq 0$ and we have divergence. 

I don't really understand why this is. Is it because $a_n$ is unbounded and so it diverges to $\infty$? I don't know a rigorous way to prove this. I'm assuming I have to make use of the theorem that monotonic $s_n$ converges iff it is bounded. 

If $a_n$ is negative, then we have that $\lim a_n = 0$

Again, I don't know how to rigorously prove this. How do I find a bound for $a_n$? 

Let $s_n = a_1 + a_2 + ... + a_n$ and $t_n = a_1 + 2 a_2 + ... + 2^k a_{2^k}$.
  For $n<2^k$, we have $s_n \geq a_1 + (a_2 + a_3) + ... _ (a_{2^k}+...+a_{2^{k+1}-1}
\geq a_1 + a_2 + ... + 2^{k}a_{2k} = t_k
$
And so $s_n \geq t_k$. 
Similar proof for $2s_{n} \leq t_k$

Someone below has already proved nonnegative decreasing case. I'm assuming that:

If $a_n$ was decreasing and negative, then $\lim a_n \neq 0$ and we have divergence.

Again, I'm not sure how to prove this. 
 A: Consider the series $\sum a_n $ where $(a_n)$ is decreasing and positive. Also, consider the series $\sum 2^n a_{2^n}$. Consider their partial sums $(s_n), (t_n)$
Note if $n < 2^n$, then $s_n = a_1 + a_2 + ... + a_n \leq a_1 + (a_2+a_3) + (a_4 + a_5 + a_6 + a_7) + ... + (a_{2^n} + ... + a_{2^{n+1}-1}) \leq a_1 + 2a_2 + ... + 2^n a_{2n} = t_n \implies \boxed{ s_n \leq t_n }$
If $2^n < n$, then $s_n  \geq a_1 + a_2 + (a_3 + a_4) + ... + (a_{2^{n-1}+1} + ... + a_{2^n} ) \geq \frac{1}{2} a_1 + a_2 + 2 a_4 + ... + 2^{n-1}a_n = \frac{1}{2} t_n \implies \boxed{ 2s_n \geq t_n }$
Since series of nonnegative terms converges iff its sequence of partial sums are bounded, then we are done.
A: Plenty of information at the Wikipedia page on this very theorem:
http://en.wikipedia.org/wiki/Cauchy_condensation_test
A: This is called the Cauchy Condensation Test. Note the convergence or divergence   of $\sum_na_n$ is unaffected by changing $a_n$ for any finite set of $n.$ So if $a_n<0$ for only finitely many n, we may substitute $0$ for $a_n$ whenever $a_n<0$ without affecting convergence or divergence. (Similarly if $a_n>0$ for finitely many $n.$) 
Also it is sufficient that $(a_n)_n$ is monotonic for all but finitely many n. ... If $(a_n)_n$ is decreasing (for all but finitely many $n$) but has negative values for infinitely many $n$ then for some $r>0$  we have:  $a_n<-r$ for all but finitely many $n$ so $\sum_na_n$ diverges, as we do not even have $a_n\to 0.$ ... I see that a proof of the Test has appeared  as an answer just now.
Examples of application:
(1). Let $a_n=n^{-K}$ for each $n.$ Then $\sum_na_n$ converges iff $K>1.$
(2).$\sum_{n>1}\frac {1}{n(\log n)^K}$ converges iff $K>1.$ 
