Let count the number of bits ‘1’ in the binary representation of . Calculate the series

**Solution**

For , consider the function:

We have:

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 iff for some integer . Thus:

The sequence defined recursively as

and counts the number of ones in the binary expansion of . Thus:

The result follows.