janmr blog

An Infinite Series Involving a Sideways Sum

I found a recent question on Mathematics Stack Exchange quite interesting. It simply asked

How does one easily calculate n=1pop(n)n(n+1)\sum\limits_{n=1}^\infty\frac{\mathrm{pop}(n)}{n(n+1)} ?

Here pop(n)\mathrm{pop}(n) denotes the “population count” or “sideways sum”, which is the number of 1s in the binary representation of nn (A000120).

The user achille hui provided a very nice answer which I would like to describe in some detail here. First, he introduces the function

θk(n)={1, if the kth bit of n is set,0, otherwise.\theta_k(n) = \begin{cases}1,&\text{ if the $k$th bit of $n$ is set,}\\0,&\text{ otherwise.}\end{cases}

which makes it possible to write the series as

n=1pop(n)n(n+1)=n=1k=0θk(n)n(n+1)=k=0n=1θk(n)n(n+1).\sum_{n=1}^\infty\frac{\mathrm{pop}(n)}{n(n+1)} = \sum_{n=1}^\infty \sum_{k=0}^\infty \frac{\theta_k(n)}{n(n+1)} = \sum_{k=0}^\infty \sum_{n=1}^\infty \frac{\theta_k(n)}{n(n+1)}.

After reversing the order of summation (which requires justification), he asks: For fixed kk, which values of nn has θk(n)=1\theta_k(n)=1? Note here that nn has the kkth bit set if and only if n/2k\lfloor n/2^k \rfloor has the zeroth bit set. And a number has the zeroth bit set if and only if that number is odd. So θk(n)=1\theta_k(n)=1 if and only if n/2k=2l+1\lfloor n/2^k \rfloor = 2 l + 1 for some l=0,1,2,l = 0, 1, 2, \ldots. This means

θk(n)=12l+1n/2k<2l+2(2l+1)2kn(2l+2)2k1,\begin{aligned} \theta_k(n)=1 \quad&\Leftrightarrow\quad 2 l + 1 \leq n/2^k < 2 l + 2 \\ &\Leftrightarrow\quad (2 l + 1) 2^k \leq n \leq (2 l + 2) 2^k - 1, \end{aligned}

for some l=0,1,2,l = 0, 1, 2, \ldots. This provides us with the intervals of nn that we are interested in, so we have

n=1pop(n)n(n+1)=k=0n=1θk(n)n(n+1)=k=0l=0n=(2l+1)2k(2l+2)2k11n(n+1)=k=0l=0n=(2l+1)2k(2l+2)2k1(1n1n+1)=k=0l=0(1(2l+1)2k1(2l+2)2k)=(k=02k)(m=1(1)m+11m)=2ln2\begin{aligned} \sum_{n=1}^\infty\frac{\mathrm{pop}(n)}{n(n+1)} &= \sum_{k=0}^\infty \sum_{n=1}^\infty \frac{\theta_k(n)}{n(n+1)} \\ &= \sum_{k=0}^\infty \sum_{l=0}^\infty \sum_{n=(2 l + 1) 2^k}^{(2 l + 2) 2^k - 1} \frac{1}{n(n+1)} \\ &= \sum_{k=0}^\infty \sum_{l=0}^\infty \sum_{n=(2 l + 1) 2^k}^{(2 l + 2) 2^k - 1} \left( \frac{1}{n} - \frac{1}{n+1} \right) \\ &= \sum_{k=0}^\infty \sum_{l=0}^\infty \left( \frac{1}{(2 l + 1) 2^k} - \frac{1}{(2 l + 2) 2^k} \right) \\ &= \left( \sum_{k=0}^\infty 2^{-k} \right) \left( \sum_{m=1}^\infty (-1)^{m+1} \frac{1}{m} \right) \\ &= 2 \ln 2 \end{aligned}

Here, both a telescoping sum, a geometric progression sum (see Nice Proof of a Geometric Progression Sum with r=1/2r=1/2) and the power series for the natural logarithm of 2 occurs.

Very nice.