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

Solution 1:

For $k \in \mathbb{N}$, consider the function:

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

We have:

$$\sum_{n=1}^{\infty} \frac{\operatorname{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)} \tag{*}$$ because the summands in the double sum are all non-negative numbers and allow us to perform the double sum in any order we want.

Notice $\theta_k(n) = 1\;$ iff $\;(2l + 1)2^k \le n < (2l+2)2^k\;$ for some integer $l \in \mathbb{N}$, we get:

$$ (*) = \sum_{k=0}^{\infty}\sum_{l=0}^{\infty} \sum_{n=(2l+1)2^k}^{(2l+2)2^k-1} \frac{1}{n(n+1)} = \sum_{k=0}^{\infty}\sum_{l=0}^{\infty} \left(\frac{1}{(2l+1)2^k} - \frac{1}{(2l+2)2^k}\right)\\ = \left(\sum_{k=0}^{\infty}2^{-k}\right)\sum_{l=0}^{\infty} \left(\frac{1}{2l+1} - \frac{1}{2l+2}\right) = \frac{1}{1-2^{-1}}\log 2 = 2\log 2 $$

Solution 2:

Personally I think you will struggle to find an exact formula because of the difficulty in establishing an expression for $\text{pop}(n)$. Here's a first attempt at some bounds...

$$1\le\text{pop}(n)\le\lfloor \log_2(n)\rfloor+1\le \frac{\ln(n)}{\ln(2)}+1,$$

$$\sum_{n=1}^{\infty}\frac{\text{pop}(n)}{n(n+1)}\le\frac{1}{\ln(2)}\sum_{n=1}^{\infty}\frac{\ln(n)}{n(n+1)}+\sum_{n=1}^{\infty}\frac{1}{n(n+1)}=\frac{1}{\ln(2)}\sum_{n=1}^{\infty}\frac{\ln(n)}{n(n+1)}+1,$$ where we used:$$\sum_{n=1}^{\infty}\frac{1}{n(n+1)}=1,$$ which also establishes the lower bound. Then note that $\ln(x)/x$ is monotone and decreasing for $x>e$ and so we can apply the integral test if we split the sum as follows:

$$\sum_{n=1}^{\infty}\frac{\ln(n)}{n(n+1)}=\frac{\ln(2)}{6}+\sum_{n=3}^{\infty}\frac{\ln(n)}{n(n+1)},$$ $$\int_{3}^{\infty}\frac{\ln(x)}{x(x+1)}{dx}\le\sum_{n=3}^{\infty}\frac{\ln(n)}{n(n+1)}\le\frac{\ln(3)}{3(3+1)}+\int_{3}^{\infty}\frac{\ln(x)}{x(x+1)}{dx},$$ $$\int _{3}^{\infty }\!{\frac {\ln \left( x \right) }{x \left( x+1 \right) }}{dx}=-\frac{1}{2}\, \ln^2 \left( 3 \right)+{ \text{dilog}} \left( 4 \right) +2\,\ln \left( 3 \right) \ln \left( 2 \right) +\frac{{\pi }^{2}}{6}\approx0.625084187,$$ therefore:

$$1\le\sum_{n=1}^{\infty}\frac{\text{pop}(n)}{n(n+1)}\le{\frac {14\,\ln \left( 2 \right) +\ln \left( 3 \right) -6\, \left( \ln \left( 3 \right) \right) ^{2}+12\,{\text{dilog}} \left( 4 \right) +24\,\ln \left( 3 \right) \ln \left( 2 \right) +2\,{\pi }^{ 2}}{12\ln \left( 2 \right) }} , $$

$$1\le\sum_{n=1}^{\infty}\frac{\text{pop}(n)}{n(n+1)}\le2.2006.$$

Solution 3:

There is one more way to calculate this expression. Consider the following recurrence: $a_0 = 0, a_1 = 1, a_2 = 1$ and $$a_{2n} = a_n, \ a_{2n+1} = a_n + 1, \ n \ge 1.$$ It is easy to see that $a_n$ counts the number of ones in the binary expansion of $n$. We wish to calculate \begin{align*} \sum_{n = 1}^{\infty} \frac{a_n}{n(n+1)} &= \sum_{n=1}^{\infty} \frac{a_{2n}}{2n(2n+1)} + \sum_{n = 0}^{\infty} \frac{a_{2n+1}}{(2n+1)(2n+2)} \\ &= \sum_{n=1}^{\infty} \frac{a_{n}}{2n(2n+1)} + \sum_{n = 0}^{\infty} \frac{a_{n} + 1}{(2n+1)(2n+2)} \\ &= \frac{1}2 + \frac{1}2 \sum_{n = 1}^{\infty} \frac{a_n}{n(2n+1)} + \frac{1}2 \sum_{n=1}^{\infty} \frac{a_n}{(n+1)(2n+1)} + \frac{1}2 \sum_{n=1}^{\infty} \frac{1}{(n+1)(2n+1)} \\ &= \frac{1}2 + \frac{1}2 \sum_{n=1}^{\infty} a_n \left( \frac{1}{n(2n+1)} + \frac{1}{(n+1)(2n+1)} \right) + \frac{1}2 \sum_{n=1}^{\infty} \frac{1}{(n+1)(2n+1)} \\ &= \frac{1}2+ \frac{1}2 \sum_{n=1}^{\infty} \frac{a_n}{n(n+1)} + \frac{1}2\sum_{n=1}^{\infty} \frac{1}{(n+1)(2n+1)}. \end{align*}

Thus, $$\sum_{n=1}^{\infty} \frac{a_n}{n(n+1)} = 1 + \sum_{n=1}^{\infty} \frac{1}{(n+1)(2n+1)}.$$

Now \begin{align*} \sum_{n=1}^{\infty} \frac{1}{(n+1)(2n+1)} &= \sum_{n=1}^{\infty} \int_0^1 \frac{x^{2n}}{n+1} \ dx \\ &= \int_0^1 \sum_{n=1}^{\infty} \frac{x^{2n}}{n+1} \ dx \\ &= \int_0^1 -\frac{ \log(1-x^2)}{x^2} \ dx -1\\ &= \log(4) - 1. \end{align*} Therefore, our desired value is $$1 + \log(4) - 1 = 2 \log(2).$$