Prove that $\sum a_n$ converges iff $\sum 2^n a_{2^n}$ converges Let $\{a_n\}$ be a positive, decreasing sequence.
How do I prove that $\sum_{n=1}^\infty a_n$ converges iff $\sum_{n=1}^\infty 2^n a_{2^n}$ converges? I don't even know where to start. Any help would be appreciated.
 A: It's all about marry...ing terms together. One way (the elements are displayed for the case $N=3$):
\begin{align}
 \sum_1^{2^N-1} a_k  & = (a_1) + \left(a_2+a_3\right)+ \left(a_4+a_5+a_6+a_7\right)\ldots \\
 & \le   a_1 + 2a_{2}+ 4a_{a}\ldots \\
& \le   \sum_0^{N-1} 2^k a_{2^k}
\end{align}
by monotony.
Return:
\begin{align}
 \sum_0^{N-1}   2^k a_{2^k} & = \left(a_1 + a_2 \right) + \left(a_2+a_4+a_4+a_4\right)+a_4\ldots \\
 & \le   \left(a_1 + a_1 \right) + \left(a_2+a_2+a_3+a_3\right)+2 a_4\ldots \\
& \le   2 \sum_1^{2^{N-1}} a_k
\end{align}
by monotony again. If one series is convergent, its limit bounds the other because the latter  is a sum  of positive terms, hence increasing and bounded, hence the other converges too.
As said in one comment, it is called Cauchy's condensation test. The figure below  illustrates the way series are bounded:

A: The proof follows by prof. Rudin's book, PMA, page 61, Theorem 3.27.
Let 
\begin{align}
s_n&=a_1+a_2+a_3+\cdots+a_n,\\
t_k&=a_1+2a_2+4a_4+\cdots+2^ka_{2^k}.
\end{align}
For $n<2^k$,
\begin{align}
s_n
&\le a_1+(a_2+a_3)+\cdots+(a_{2^{k}}+\cdots+a_{2^{k+1}-1})\\
&\le a_1+2a_2+\cdots+2^ka_{2^k}\\
&=t_k.
\end{align}
On the other hand, for $2^k<n$,
\begin{align}
s_n
&\ge a_1+a_2+(a_3+a_4)+\cdots+(a_{2^{k-1}+1}+\cdots+a_{2^{k}})\\
&\ge \frac{1}{2}a_1+a_2+2a_4+\cdots+2^{k-1}a_{2^k}\\
&=\frac{1}{2}t_k.
\end{align}
Therefore the sequences $\{s_n\}$ and $\{t_k\}$ are either both bounded or
both unbounded, which implies $\sum a_n$ and $\sum 2^na_{2^n}$ are either
both convergent or both divergent.
A: Since the sequence is positive and decreasing, for each $n$ we have
$$2^na_{2^n} = 2 \cdot 2^{n-1}a_{2^n} = 2 \sum_{i=2^{n-1}+1}^{2^n} a_{2^n} \le 2 \sum_{i=2^{n-1}+1}^{2^n} a_i$$
Summing over $n$ then yields
$$\sum_{n=1}^{\infty} 2^na_{2^n} \le 2 \sum_{i=1}^{\infty} a_i$$
So your series converges.
