janmr blog

An Infinite Series Involving a Sideways Sum

I found a recent question on Mathematics Stack Exchange quite interesting. It simply asked

How does one easily calculate ?

Here denotes the “population count” or “sideways sum”, which is the number of 1s in the binary representation of (A000120).

The user achille hui provided a very nice answer which I would like to describe in some detail here. First, he introduces the function

which makes it possible to write the series as

After reversing the order of summation (which requires justification), he asks: For fixed , which values of has ? Note here that has the th bit set if and only if has the zeroth bit set. And a number has the zeroth bit set if and only if that number is odd. So if and only if for some . This means

for some . This provides us with the intervals of that we are interested in, so we have

Here, both a telescoping sum, a geometric progression sum (see Nice Proof of a Geometric Progression Sum with ) and the power series for the natural logarithm of 2 occurs.

Very nice.