2

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?

Community
  • 1
Chern-Simons
  • 927
  • 2
    You made a mistake in jumping to (5) from (4). A term like that does not appear because the length of the sums in (4) (which are hidden in the "...") varies with $n$. So for instance to get a $-4$ in a denominator requires $n$ at least $2$. –  Apr 17 '20 at 17:27
  • 2
    Just write the occurring terms down, starting with $n=0$: $r=2^0=2^1-1=1$; $n=1$: $r=2,\ 3$; $n=2$: $r=4,\ 5,\ 6,\ 7$, .... so you never devide trough $0$. – mag Apr 17 '20 at 17:32

2 Answers2

3

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.

Parcly Taxel
  • 103,344
  • Thanks. So does that imply $\sum^N_{n=0}\sum^{2^{n+1}-1}{r=2^n}\frac{1}{r} \neq \sum^N{n=0}\left(\frac{1}{2^n}\right)+\sum^N_{n=0}\left(\frac{1}{2^n+1}\right)+...+\sum^N_{n=0}\left(\frac{1}{2^{n+1}-2}\right)+\sum^N_{n=0}\left(\frac{1}{2^{n+1}-1}\right)$? – Chern-Simons Apr 17 '20 at 18:14
  • 1
    @Simons-Chern Yes. – Parcly Taxel Apr 17 '20 at 18:14
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}

CHAMSI
  • 8,333
  • Thanks. How is $S_0$ defined by the way? – Chern-Simons Apr 17 '20 at 18:51
  • 2
    It is an empty sum, by convention, $ \sum\limits_{i\in\emptyset}{x_{i}}=0 $, and $ \prod\limits_{i\in\emptyset}{x_{i}}=1 \cdot $

    https://en.wikipedia.org/wiki/Empty_sum

    If you do not want to deal with $ S_{0} $, you can remove the first term $\left(n=0\right) $ from the sum, from the begining.

     – CHAMSI Apr 17 '20 at 19:27