11
$\begingroup$

I'm now stuck with this question, and I don't even know where to start: Find sum of series$$\sum_1^\infty \frac{f(n)}{n(n+1)}$$, where f(n) - number of ones in binary representation of n.

I wish I could post some moves, that I've tried but I don't know what to do.

Thanks!

$\endgroup$
4
  • $\begingroup$ Do you just need to show it converges, or do you actually need to find the sum? $\endgroup$ Commented Mar 11, 2015 at 12:13
  • $\begingroup$ Find the sum. Show convergence is not a problem) $\endgroup$ Commented Mar 11, 2015 at 12:22
  • $\begingroup$ super question! $\endgroup$
    – RE60K
    Commented Mar 11, 2015 at 12:34
  • $\begingroup$ I sense a recursion... $\endgroup$
    – shardulc
    Commented Mar 11, 2015 at 13:00

2 Answers 2

21
$\begingroup$

Maybe there is a quicker way, but here is one. Let the sum be $S$. We have $$\frac{f(n)}{n(n+1)} = \frac{f(n)}{n}-\frac{f(n)}{n+1}$$ $$\implies \frac{f(2n)}{(2n)(2n+1)}+\frac{f(2n+1)}{(2n+1)(2n+2)} = \frac{f(2n)}{2n}-\frac{f(2n)-f(2n+1)}{2n+1}-\frac{f(2n+1)}{2n+2}$$

Now $f(2n+1) = f(2n)+1, \; f(2n) = f(n)$, so we can write: $$\frac{f(2n)}{(2n)(2n+1)}+\frac{f(2n+1)}{(2n+1)(2n+2)} = \frac{f(2n)}{2n}+\frac1{2n+1}-\frac{f(2n)+1}{2n+2} \\ = \frac12\left(\frac{f(n)}n -\frac{f(n)}{n+1}\right)+\left(\frac1{2n+1}-\frac1{2n+2}\right)$$

$$\implies S = \frac12+ \frac12\sum_{n=1}^\infty \frac{f(n)}{n(n+1)}+\sum_{n=1}^\infty \left(\frac1{2n+1}-\frac1{2n+2}\right) $$ $$\implies 2S = 1 + S + 2\log 2 -1 \implies S = 2\log 2 \approx 1.386$$

$\endgroup$
3
  • $\begingroup$ Wow! Thank you a lot! $\endgroup$ Commented Mar 11, 2015 at 14:30
  • $\begingroup$ @Macavity I wanted to ask, is there any materials to learn how to solve such sums? $\endgroup$ Commented Mar 11, 2015 at 14:43
  • $\begingroup$ @DoctorMoisha Can't say there is one book which I could suggest - I have found useful methods to sum from many areas. Maybe you should separately ask for a list of books, the community here may recommend better. $\endgroup$
    – Macavity
    Commented Mar 11, 2015 at 14:55
3
$\begingroup$

Code:

double sum=0;
for(int i=1;i<9999999;i++){
    double s2=Integer.bitCount(i);
    sum+=(s2)/(i*(i+1));
}

Output Data

$$\begin{array}{r|l} n&\sum\\\hline 9&1.065079365079365\\ 99&1.3394382621894894\\ 999&1.3800972409478014\\ 9999&1.3854974129587205\\ 99999&1.3852676077956714\\&(\text{limit of data type, therefore decreased value}) \end{array}$$

$\endgroup$
3
  • 1
    $\begingroup$ Oh, neat) Although, I need proof. I wonder what is this number... $\endgroup$ Commented Mar 11, 2015 at 13:26
  • 1
    $\begingroup$ @DoctorMoisha: If you get some more accurate digits, you can use the inverse symbolic calculator $\endgroup$ Commented Mar 11, 2015 at 14:18
  • $\begingroup$ @ADG you should probably be using a long integer (assuming that's java) for i. Good answer, though! $\endgroup$
    – k_g
    Commented Mar 11, 2015 at 22:57

You must log in to answer this question.

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