Why does $\sum^N_{n=0}\frac12\leq\sum^N_{n=0}\sum^{2^{n+1}-1}_{r=2^n}\frac1r\leq\sum^N_{n=0}1=\frac{N+1}2\leq\sum^{2^{N+1}-1}_{r=1}\frac1r\leq N+1$?

Question

Consider the following inequalities:

$$\frac{1}{2} \leq \sum^{2^{n+1}-1}_{r=2^n}\frac{1}{r}\leq 1 \tag{1}$$ Upon summing over $(1)$ from $n=0$ to $n=N$, we obtain $$\sum^N_{n=0}\frac{1}{2}\leq \sum^N_{n=0}\sum^{2^{n+1}-1}_{r=2^n}\frac{1}{r}\leq\sum^N_{n=0}1 \tag{2}$$ or equivalently $$\frac{N+1}{2}\leq\sum^{2^{N+1}-1}_{r=1}\frac{1}{r}\leq N+1 \tag{3}$$

But I do not see how one can proceed from the double sum in $(2)$ to the single sum in $(3)$?

I tried to make sense of $(3)$ by directly expanding the summation terms in $(2)$:

$$S=\sum^N_{n=0}\sum^{2^{n+1}-1}_{r=2^n}\frac{1}{r}=\sum^N_{n=0}\left(\frac{1}{2^n}+\frac{1}{2^n+1}+...+\frac{1}{2^{n+1}-2}+\frac{1}{2^{n+1}-1} \right) \tag{4}$$

However, further expansion followed by applying the sum to each term of $(4)$ individually led to the following predicaments:

$1.$ Sums like $$\sum^N_{n=0}\left(\frac{1}{2^{n+1}-4}\right) \tag{5}$$ contain one or more terms that are undefined and so do not make any sense.

*Can we circumvent this by ignoring terms that appear before and including the 'trouble-causing' term, e.g. in the case of $(5)$ $$\sum^N_{n=0}\left(\frac{1}{2^{n+1}-4}\right) \to \sum^N_{n=2}\left(\frac{1}{2^{n+1}-4}\right) \tag{6}$$ ?

$2.$ There are repeated terms generated by $(4)$ and they do not cancel,and are therefore inconsistent with $(3)$?

e.g. $1$ appears twice due to $\sum^N_{n=0} \left(\frac{1}{2^n}\right)$ and $\sum^N_{n=0} \left(\frac{1}{2^n+1} \right)$

Can someone please explain where my conceptual errors lie?

Answer 1

The number of terms within the inner sums changes with the outer sum, and this prevents zero denominators.

• At $n=0$, $r$ can only be $1$.
• At $n=1$, $r$ can only be $2$ or $3$ (numbers with $2$ bits).
• At $n=2$, $r$ can only be $4,5,6,7$ (numbers with $3$ bits), etc.

Continuing, we find that the double sum is in fact over all $r$ from $1$ to $2^{N+1}-1$, without gaps, hence can be reduced to the single sum.

Answer 2

In fact it is a $\underline{\textbf{telescopic sum}}$, let $ N\in\mathbb{N} $, denoting for any $ n\in\mathbb{N} $, $ S_{n}=\sum\limits_{k=1}^{2^{n}-1}{\frac{1}{k}} $, we have : \begin{aligned}\sum_{n=0}^{N}{\sum_{r=2^{n}}^{2^{n+1}-1}{\frac{1}{r}}}&=\sum_{n=0}^{N}{\left(\sum_{r=1}^{2^{n+1}-1}{\frac{1}{r}}-\sum_{r=1}^{2^{n}-1}{\frac{1}{r}}\right)}\\ &=\sum_{n=0}^{N}{\left(S_{n+1}-S_{n}\right)}\\ &=S_{N+1}-S_{0}\\\sum_{n=0}^{N}{\sum_{r=2^{n}}^{2^{n+1}-1}{\frac{1}{r}}}&=\sum_{n=0}^{2^{N+1}-1}{\frac{1}{r}}\end{aligned}