Home » Uncategorized » Series with number of bits ‘1’

Series with number of bits ‘1’

Let {\rm pop} count the number of bits ‘1’ in the binary representation of n. Calculate the series

    \[\mathcal{S} = \sum_{n=1}^{\infty} \frac{{\rm pop}(n)}{n(n+1)}\]

Solution

For k \in \mathbb{N}, consider the function:

    \[\theta_k(n) = \left\{\begin{matrix} 1 & , & \text{if k-th bit of n is set} \\ 0 & , & \text{otherwise} \end{matrix}\right.\]

We have:

    \[\sum_{n=1}^{\infty} \frac{\operatorname{pop}(n)}{n(n+1)} = \sum_{n=1}^{\infty}\sum_{k=0}^{\infty} \frac{\theta_k(n)}{n(n+1)} =  \sum_{k=0}^{\infty}\sum_{n=1}^{\infty} \frac{\theta_k(n)}{n(n+1)}\]

because the summands in the double sum are all non-negative numbers and allow us to perform the double sum in any order we want.

Notice \theta_k(n) = 1 iff (2\ell+ 1)2^k \leq n < (2\ell+2)2^k for some integer \ell \in \mathbb{N}. Thus:

    \begin{align*} \sum_{k=0}^{\infty}\sum_{\ell=0}^{\infty} \sum_{n=(2\ell+1)2^k}^{(2\ell+2)2^k-1} \frac{1}{n(n+1)} &= \sum_{k=0}^{\infty}\sum_{\ell=0}^{\infty} \left(\frac{1}{(2\ell+1)2^k} - \frac{1}{(2\ell+2)2^k}\right)\\ &= \left(\sum_{k=0}^{\infty}2^{-k}\right)\sum_{\ell=0}^{\infty} \left(\frac{1}{2l+1} - \frac{1}{2l+2}\right) \\ &= \frac{1}{1-2^{-1}}\log 2 \\ &= 2\log 2 \end{align*}

Read more

1 Comment

Leave a comment

Donate to Tolaso Network