Determine the following sum

Question

Let $S(n)$ be the sum of the digits of n in its binary representation. For example the binary notation for 19 is $10011$ and $S(19)=3$. Determine $\sum_{n=1}^{\infty} \frac{S(n)}{n(n+1)}$?

I've made several tables trying to pinpoint any useful pattern, but I've had minimal luck. The best I'd came to was determining that the number of digits is $\left \lceil{\frac{ln(n)}{ln(2)}}\right \rceil$ which gives a bound for $S(n)$. What I'd picked up from those tables is $S(2^k-1)=k$ and $S(2^k)=1$. However, breaking the sum up into those n's that are powers of 2 proved to be a bit of a disaster.

Answer 1

The key idea is to expand over digits and find a recurrence. Let $$\require{cancel}F(N)=\sum_{n=1}^{2^N}{\frac{S(n)}{n(n+1)}}=\sum_{n=1}^{2^N}{S(n)\left(\frac{1}{n}-\frac{1}{n+1}\right)}$$ and \begin{align*} G(N)&=\sum_{n=0}^{2^{N-1}-1}{\left(\frac{1}{2n+1}-\frac{1}{2n+2}\right)}-\left(\frac{1}{2^N+1}-\frac{1}{2^N+2}\right) \\ &=\sum_{n=1}^{2^N}{\frac{(-1)^{n+1}}{n}}-\frac{1}{(2^N+1)(2^N+2)}\text{;} \end{align*} we know that $\lim_{N\to\infty}{G(N)}=\ln{(2)}$ and want to find $\lim_{N\to\infty}{F(N)}$.

We can compute \begin{align*} F(N)&=\sum_{n\in[2^N],2\mid n}{S(n)\left(\frac{1}{n}-\frac{1}{n+1}\right)}+\sum_{n\in[2^N],2\nmid n}{S(n)\left(\frac{1}{n}-\frac{1}{n+1}\right)} \\ &=\sum_{n=1}^{2^{N-1}}{S(2n)\left(\frac{1}{2n}-\frac{1}{2n+1}\right)}+\sum_{n=0}^{2^{N-1}-1}{S(2n+1)\left(\frac{1}{2n+1}-\frac{1}{2n+2}\right)} \\ &=\sum_{n=1}^{2^{N-1}}{S(n)\left(\frac{1}{2n}-\frac{1}{2n+1}\right)}+\sum_{n=0}^{2^{N-1}-1}{(1+S(n))\left(\frac{1}{2n+1}-\frac{1}{2n+2}\right)} \\ &=\sum_{n=1}^{2^{N-1}}{S(n)\left(\frac{1}{2n}-\cancel{\frac{1}{2n+1}}+\cancel{\frac{1}{2n+1}}-\frac{1}{2n+2}\right)}-\left(\frac{1}{2^N+1}-\frac{1}{2^N+2}\right)+ \\ &\phantom{{}={}}\quad\sum_{n=0}^{2^{N-1}-1}{\left(\frac{1}{2n+1}-\frac{1}{2n+2}\right)} \\ &=\frac{F(N-1)}{2}+G(N) \\ &=\frac{F(0)}{2^N}+\frac{G(1)}{2^{N-1}}+\dots+\frac{G(N-1)}{2}+G(N) \\ &=\frac{1}{2^{N+1}}+\sum_{k=0}^{N-1}{\frac{G(N-k)}{2^k}} \end{align*} Thus $$|F(N)-\ln{(2)}|\leq\frac{1}{2^{N+1}}+\sum_{k=0}^{N-1}{\frac{|G(N-k)-\ln{(2)}|}{2^k}}+\sum_{k=N}^{\infty}{\frac{\ln{(2)}}{2^k}}$$ The outer two terms are clearly tending to $0$ as $N\to\infty$, so it suffices to show the same for the inner.

Fix $\epsilon$. There exists $K$ such that, for $k\geq K$, we have $|G(k)-\ln{(2)}|\leq\epsilon$; let $M=\sup_{k<K}{G(k)}$. Then \begin{align*} \sum_{k=0}^{N-1}{\frac{|G(N-k)-\ln{(2)}|}{2^k}}&=\sum_{k=1}^N{\frac{|G(k)-\ln{(2)}|}{2^{N-k}}} \\ &\leq\sum_{k=0}^{K-1}{\frac{M}{2^{N-k}}}+\sum_{k=K}^N{\frac{\epsilon}{2^{N-k}}} \\ &\leq\frac{(2^K-1)M}{2^N}+\frac{\epsilon}{2^{K-1}} \end{align*} Thus $\limsup_{N\to\infty}{|F(N)-\ln{(2)}|}\leq\epsilon$; now take $\epsilon\to0^+$ to get $$\lim_{N\to\infty}{F(N)}=\ln{(2)}$$

Of course, we selected a subsequence of partial sums to get $F(N)$, so theoretically the unselected partial sums could exhibit $\Theta(1)$ variation from $F(N)$. But each term in your original sum is nonnegative, so in fact that can't happen.

Answer 2

$$F=\sum\limits_{n=1}^\infty\frac{S(n)}{n(n+1)}$$

This series is absolutely convergent since terms are positive and $S(n)=O(\log_2(n))$, making the general term $O\left(\frac{\ln(n)}{n^2}\right)$. Therefore we are allowed to manipulate the series and rearrange terms at will.

Notice that multiplying a number by $2$ will simply shift the binary development to the left and add a zero.

This does not change the value of the sum of digits so $\begin{cases}S(2n)=S(n)\\S(2n+1)=S(2n)+1=S(n)+1\end{cases}$

Let split $F$ along odd and even indexes:

$\begin{align}\displaystyle F &=\frac{S(1)}2+\sum\limits_{n=1}^\infty\bigg(\frac{S(2n)}{2n(2n+1)}+\frac{S(2n+1)}{(2n+1)(2n+2)}\bigg)\\\\ &=\frac 12+\frac 12\sum\limits_{n=1}^\infty\bigg(\frac{S(n)}{n(2n+1)}+\frac{S(n)+1}{(2n+1)(n+1)}\bigg)\\\\ &=\frac 12+\frac 12\sum\limits_{n=1}^\infty S(n)\Big(\underbrace{\frac 1{n(2n+1)}+\frac 1{(2n+1)(n+1)}}_{\frac 1{n(n+1)}}\Big)+\sum\limits_{n=1}^\infty\underbrace{\frac 1{(2n+1)(2n+2)}}_{\frac 1{2n+1}-\frac 1{2n+2}}\end{align}$

The first series is $\frac 12F$ so we arrive to a formulation without $S(n)$.

$$F=1+2\sum\limits_{n=1}^\infty\bigg(\frac 1{2n+1}-\frac 1{2n+2}\bigg)\\$$

Beware it is NOT telescopic, but we can use $\int_0^1 x^n=\frac 1{n+1}$ and $\sum x^n=\frac 1{1-x}$. Note that in what's follow we can swap $\int$ and $\sum$ thanks to Fubini-Tonelli combined with absolute convergence.

$\begin{align}\displaystyle F &=1+2\sum\limits_{n=1}^\infty\int_0^1\Big(x^{2n}-x^{2n+1}\Big)dx =1+2\int_0^1(1-x)\Big(\sum\limits_{n=1}^\infty x^{2n}\Big)dx\\\\ &=1+2\int_0^1 (1-x)\frac{x^2}{1-x^2}dx=1+2\int_0^1 \frac{x^2}{x+1}dx\\\\ &=1+2\bigg[\tfrac 12 x^2-x+\ln(x+1)\bigg]_0^1=1+2\Big(\ln(2)-\tfrac 12\Big) \end{align}$

$$F=2\ln(2)$$