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$ Mar 11, 2015 at 12:13
  • $\begingroup$ Find the sum. Show convergence is not a problem) $\endgroup$ Mar 11, 2015 at 12:22
  • $\begingroup$ super question! $\endgroup$
    – RE60K
    Mar 11, 2015 at 12:34
  • $\begingroup$ I sense a recursion... $\endgroup$
    – shardulc
    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$ Mar 11, 2015 at 14:30
  • $\begingroup$ @Macavity I wanted to ask, is there any materials to learn how to solve such sums? $\endgroup$ 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
    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$ Mar 11, 2015 at 13:26
  • 1
    $\begingroup$ @DoctorMoisha: If you get some more accurate digits, you can use the inverse symbolic calculator $\endgroup$ 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
    Mar 11, 2015 at 22:57

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.