10
$\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$
  • $\begingroup$ Do you just need to show it converges, or do you actually need to find the sum? $\endgroup$ – Gregory Grant Mar 11 '15 at 12:13
  • $\begingroup$ Find the sum. Show convergence is not a problem) $\endgroup$ – DoctorMoisha Mar 11 '15 at 12:22
  • $\begingroup$ super question! $\endgroup$ – RE60K Mar 11 '15 at 12:34
  • $\begingroup$ I sense a recursion... $\endgroup$ – shardulc Mar 11 '15 at 13:00
20
$\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$
  • $\begingroup$ Wow! Thank you a lot! $\endgroup$ – DoctorMoisha Mar 11 '15 at 14:30
  • $\begingroup$ @Macavity I wanted to ask, is there any materials to learn how to solve such sums? $\endgroup$ – DoctorMoisha Mar 11 '15 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 '15 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$
  • 1
    $\begingroup$ Oh, neat) Although, I need proof. I wonder what is this number... $\endgroup$ – DoctorMoisha Mar 11 '15 at 13:26
  • 1
    $\begingroup$ @DoctorMoisha: If you get some more accurate digits, you can use the inverse symbolic calculator $\endgroup$ – Ross Millikan Mar 11 '15 at 14:18
  • $\begingroup$ @RossMillikan Thanks! $\endgroup$ – DoctorMoisha Mar 11 '15 at 14:29
  • $\begingroup$ @ADG you should probably be using a long integer (assuming that's java) for i. Good answer, though! $\endgroup$ – k_g Mar 11 '15 at 22:57
  • $\begingroup$ @k_g yes thanks $\endgroup$ – RE60K Mar 12 '15 at 9:34

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.