14
$\begingroup$

We are given the series $\sum_{n=1}^\infty {\frac {f(n)} {n(n+1)}}$, where $f(n)$ is such a function that it equals the sum of 1's in the binary representation of n.

I'm obliged to find the sum of the series. First, I decided to explicitly prove the convergence of the series. Use for that converging harmonic series,

$\sum {\frac 1 {n^2}}$.
$\lim_{n \to \infty} \frac {f(n)* n^2} {n \cdot (n+1)} = \lim_{n \to \infty} f(n)$

Where $f(n)$ could be represented as $\sum_{i=0}^{\log_2 n} m_i$, if we define n as $\sum_{i=0}^{\log_2 n} m_i \cdot 2^i$ and $m_i$ is able to take values of 0 or 1.

I can get it intuitively that $f(n)$ doesn't yield $\infty$, when $n \to \infty$. A graph of the function would behave like wave, growing and then returning to 1. I wrote a script to get some sense of the data, which outputted:

For p= 10 series= 1.0873015873015872
For p= 100 series= 1.3398423025935298
For p= 1000 series= 1.3801052489558094
For p= 100000 series= 1.3861981879674006

This result looks for me like $ln(4)$, but it doesn't help much, since the solution is supposed to be purely analytical. How can I find a sum?

$\endgroup$
8
  • 4
    $\begingroup$ As for convergence, we can prove that $f(n)\le \log_2(n+1)$, and the series $\sum_{n\ge 1}\frac{\ln n}{n^2}$ converges. $\endgroup$ Mar 16, 2014 at 9:30
  • $\begingroup$ For a graph of $f(n)$, see OEIS A000120 $\endgroup$
    – Henry
    Mar 16, 2014 at 9:33
  • $\begingroup$ $f(n)$ is max$\{r\in\mathbb N:2^r | \binom{2n}n\}$ $\endgroup$
    – ajotatxe
    Mar 16, 2014 at 9:48
  • $\begingroup$ @user2425 Would you clarify your comment, pls? Probably I'm failing to understand it. f(10)=2. But I can't get 2 from your formula: binomial(20,10) gives 184756 and... "|" is logical or? $\endgroup$
    – Dmitri K
    Mar 16, 2014 at 10:10
  • $\begingroup$ @wf34 it means that $2^r$ divides ${2n\choose n}$. $\endgroup$ Mar 16, 2014 at 10:46

1 Answer 1

17
$\begingroup$

Let $S$ be the sum (which exists as already noted in the comments). Use that $f(2n)=f(n)$ and $f(2n+1)=f(n)+1$. Then splitting the sum in $n$ even and $n$ odd and grouping terms results in the recursion $S= \log(2)+\tfrac{1}{2}S$ so $S = 2\log(2)=\log(4)$.

$$ \begin{eqnarray} S&=&\sum_{n=1}^\infty \frac{f(n)}{n(n+1)}\\ &=&\sum_{n=0}^\infty \frac{1+f(n)}{(2n+1)(2n+2)} + \sum_{n=1}^\infty \frac{f(n)}{2n(2n+1)}\\ &=&\sum_{n=0}^\infty\left(\frac{1}{2n+1}-\frac{1}{2n+2}\right)+\sum_{n=1}^\infty f(n)\left(\frac{1}{(2n+1)(2n+2)}+\frac{1}{2n(2n+1)}\right)\\ &=&\log(2) +\sum_{n=1}^\infty\frac{f(n)}{2n(n+1)}\\ &=&\log(2)+\tfrac{1}{2}S \end{eqnarray} $$

$\endgroup$
1
  • $\begingroup$ $\sum_{i=1}^\infty \frac {f(n)} {n \cdot (n+1)}= \sum_{i=1}^\infty \frac {f(2n)} {(2n) \cdot (2n+1)} + \sum_{i=0}^\infty \frac {f(2n+1)} {(2n+1) \cdot (2n+2)} = \sum_{i=1}^\infty \frac {f(n)} {(2n) \cdot (2n+1)} +\sum_{i=0}^\infty \frac {f(n)+1} {(2n+1) \cdot (2n+2)}$ Grouping these terms led me nowhere. Would you give me some extra pointers on how get to your final expression and also why natural logarithm happened to appear in the formula? $\endgroup$
    – Dmitri K
    Mar 16, 2014 at 12:00

You must log in to answer this question.

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