27
$\begingroup$

How does one [easily] calculate $\sum\limits_{n=1}^\infty\frac{\mathrm{pop}(n)}{n(n+1)}$, where $\mathrm{pop}(n)$ counts the number of bits '1' in the binary representation of $n$? Is there any trick to calculate the sum? From what I already have, it definitely converges.

$\endgroup$
6
  • $\begingroup$ Please show why it converges. $\endgroup$
    – Did
    Jun 29, 2013 at 11:08
  • $\begingroup$ I can offer a proof of convergence if needs be... $\endgroup$ Jun 29, 2013 at 11:12
  • 3
    $\begingroup$ @Graham Me too. :-) But it would be best if the OP did... $\endgroup$
    – Did
    Jun 29, 2013 at 11:14
  • 3
    $\begingroup$ @Did, let $a_n = \frac{\mathrm{pop}(n)}{n(n+1)}$, $b_n = \frac{\lfloor \log_{2}{k} \rfloor + 1}{n(n+1)}$, and $\forall n \in \mathbb{N}: a_n \leq b_n$. And as we know that $b_n$ converges, we can conclude that $a_n$ converges. It's rather rough, but that's what I have. P.S. thanks for editing my post. $\endgroup$
    – tkroman
    Jun 29, 2013 at 11:32
  • 1
    $\begingroup$ @GrahamHesketh, "I do because I can", that's all. Just found it interesting, but found myself unable to figure out a nice analytic formula. $\endgroup$
    – tkroman
    Jun 29, 2013 at 13:51

3 Answers 3

48
$\begingroup$

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 $$

$\endgroup$
4
  • 2
    $\begingroup$ Thank you, it looks elegant. $\endgroup$
    – tkroman
    Jun 29, 2013 at 13:33
  • $\begingroup$ Beat me to it. (+1) $\endgroup$
    – robjohn
    Jun 29, 2013 at 13:43
  • $\begingroup$ The step before the last one where you consider the two sum separately, is that correct? I mean the parenthesis you put is correct? $\endgroup$
    – J. P. C.
    Mar 31, 2017 at 9:23
  • $\begingroup$ Ahh nothing I see $\endgroup$
    – J. P. C.
    Mar 31, 2017 at 9:24
7
$\begingroup$

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.$$

$\endgroup$
2
  • $\begingroup$ This approach has some interesting ideas but I've written some code: (1..1000000).inject(0){|acc, cur| acc += cur.to_s(2).count('1').to_f/(cur*cur + cur)} => 1.3862831558809863 (Ruby), that shows that value is 2 * ln 2. $\endgroup$
    – tkroman
    Jun 29, 2013 at 12:53
  • $\begingroup$ Yes you were correct, I was historically exploring what would happen if half of them were $1$ and I had forgotten to take the half out on the upper bound. Fixed now. $\endgroup$ Jun 29, 2013 at 13:38
6
$\begingroup$

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).$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .