# If $\{a_n\}_{n =1}^{\infty}$ is M-decreasing where $a_i \geq 0$, $\sum_{n =1}^{\infty}$ converges iff $\sum_{k=0}^{\infty} 2^ka_{2^k}$ converges

If $$\{a_n\}_{n =1}^{\infty}$$ is a monotone decreasing sequence where $$a_i \geq 0$$ Then $$\sum_{n =1}^{\infty}$$ converges iff $$\sum_{k=0}^{\infty} 2^ka_{2^k}$$ converges.

My issue has to do with one particular concept of the proof. To do the proof we end up showing that the partial sums are each bounded. We define our partial sums as such:

$$s_n = a_1 + a_2 + a_3 +.....+a_n \\ t_k = a_1 + 2a_2 + ...2^{k}a_{2^k}$$

In the proof we have scenarios where we let $$n > 2^k$$ and let $$n < 2^k$$

This is where I have two issues:

i) Why are we able to allow the partial sums for $$s_n$$ and $$t_k$$ to be of different lengths?

ii) in showing that $$s_n > t_k$$ we arrive at the conclusion that $$2s_n > t_k$$. Yes this shows that $$t_k$$ is bounded, but that is with regards to $$2s_n$$ that is NOT with regards to $$s_n$$ which is what I am trying to use as a comparison. So why are these things valid to do?

The statement considers two different series: $$S = \sum_{n\geqslant 1}\, a_n$$ and $$T = \sum_{k\geqslant 0}\, 2^k\,a_{2^k}$$. Then $$s_n$$ are the partial sums of $$S$$ and the $$t_k$$ are the partial sums of $$T$$. Remember that some series is said to converge if the sequence of its partial sums converge.

Now, both $${(s_n)}_{n\in\Bbb N}$$ and $${(t_k)}_{k\in\Bbb N}$$ are monotone increasing sequences. In order to show that one such sequence converges, it suffices to show that it admits an upper bound (why?).

Assume that $${(s_n)}_{n\in\Bbb N}$$ converges, so that $$S\geqslant s_n$$ for all $$n$$. If for each $$k\in\Bbb N$$ you can find some $$n\in\Bbb N$$ with $$t_k \leqslant s_n$$, then for each $$k\in \Bbb N$$ we have $$t_k \leqslant S$$. In other words, if we know that $$S$$ converges, showing that $$t_k$$ is bounded 'with regards to $$s_n$$' (or a multiple of it) implies that the sequence $${(t_k)}_{k\in\Bbb N}$$ has an upper bound (because the $$s_n$$ also do), and hence $$T$$ converges.

Something similar holds when one assumes the case that $${(t_k)}_{k\in\Bbb N}$$ converges.

EDIT: For the argument above in particular, that the $$a_n$$ are monotonically decreasing is not needed. However, we use it in this specific case for producing the bounds of one sequence in terms of the other.

For $$n\geqslant 0$$, consider the sequences $$s_{2^{n+1}-1}$$ and $$t_n$$. We have

$$\begin{array}{ccccccc} s_{2^{n+1}-1} &=& a_1 &+& (a_2 + a_3) &+& (a_4 + a_5 + a_6 + a_7) &+& \dots &+& \big(a_{2^n} + \dots + a_{2^{n+1}-1}\big)\\ t_{n} &=& a_1 &+& 2a_2 &+& 4a_4 &+& \dots &+& 2^n a_{2^n} \end{array}$$

From $$a_n \geqslant a_{n+1}$$, it's easy to see that $$t_n \geqslant s_{2^{n+1}-1}$$, so our prior argument shows that if $$T$$ converges, so must $$S$$.

Similarly, we have

$$\begin{array}{ccccccc} 2s_{2^n} &=& a_1 &+& (a_1 + a_2) &+& (a_2 + 2a_3 + a_4) &+& \dots \\ t_{n} &=& a_1 &+& 2a_2 &+& 4a_4 &+& \dots &&, \end{array}$$

so that from $$a_n \geqslant a_{n+1}$$ we conclude that $$2s_{2^n} \geqslant t_n$$. Once again, our prior argument shows that if $$S$$ converges, so must $$T$$, which concludes the proof.

• So from what I gather in your explanation, the important idea hiding in the background is the fact that these are going to infinity and as such we can find a $k \in \mathbb{N}$ that would match up with some $n\in \mathbb{N}$. The fact that the sequence converges is not affected by a constant because the sequnce would still converge regardless, just at a different pace....So then why is it important that the sequence $\{a_n\}$ be monotonically decreasing? – dc3rd Oct 25 '18 at 5:10
• I have edited the answer with an additional explanation showing where monotonicity comes into play. – Fimpellizieri Oct 29 '18 at 4:34