26
$\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$
  • $\begingroup$ Please show why it converges. $\endgroup$ – Did Jun 29 '13 at 11:08
  • $\begingroup$ I can offer a proof of convergence if needs be... $\endgroup$ – Graham Hesketh Jun 29 '13 at 11:12
  • 3
    $\begingroup$ @Graham Me too. :-) But it would be best if the OP did... $\endgroup$ – Did Jun 29 '13 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 '13 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 '13 at 13:51
44
$\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$
  • 2
    $\begingroup$ Thank you, it looks elegant. $\endgroup$ – tkroman Jun 29 '13 at 13:33
  • $\begingroup$ Beat me to it. (+1) $\endgroup$ – robjohn Jun 29 '13 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 '17 at 9:23
  • $\begingroup$ Ahh nothing I see $\endgroup$ – J. P. C. Mar 31 '17 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$
  • $\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 '13 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$ – Graham Hesketh Jun 29 '13 at 13:38
4
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.