Sum of set bits in every element for a natural numbers I was thinking of a mathematical puzzle with binary representation of numbers, but could not find a convincing answer myself. 
Here is the puzzle: Say for some number N, I want to find the sum of the set bits of every number from 1 to N.
For example, for 5
The answer would be: 7 by the following procedure
1 - 1 set bit
2 - 1 set bit
3 - 2 set bits
4 - 1 set bit
5 - 2 set bits

So answer is 1 + 1 + 2 + 1 + 2 = 7

I found that it's easy to just go one by one and add, like I did. I also found that for a number having x bits, they form the pascal triangle with set ones, if number of occurances are counted with same number of set bits, irrespective of value. For example, 
when x = 1, we have {1} - 1 set bit occurs once, hence 1.
when x = 2, we have {10, 11} - 1 set bit occurs once, 2 set bits occurs once, hence 1 1
when x = 3, we have {100, 101, 110, 111} - 1 set bit occurs once, 2 set bits occur twice, and 3 set bits occur once, hence 1 2 1

This series is continued. However, summing these up will give me a range, inside of which the answer lies. (Example ans is in [8, 15])
My first solution is the naive approach. Second one is a little mathematical, but not very fruitful.
I was wondering if we could derive a formula any N?

$F(0) = 0.$
If $2^k \le n \lt 2^{k+1}$, then $F(n) = F(n - 2^k) + F(2^k - 1) + n - 2^k + 1$.
Since $F(2^k -1) = k\,2^{k-1}$, we have $F(n) = F(n-2^k) + k\,2^{k-1} + n - 2^k + 1$.
The recursion works because the numbers between $2^k$ and $n$ all have their highest bit set (those bits give the $n - 2^k + 1$ part of the sum), and the sum of the other bits of those numbers is $F(n - 2^k)$, and the remaining numbers are taken care of by the $F(2^k-1)$ term.
The formula for $F(2^k-1)$ works because each of the $k$ bits of the numbers in ${0, 1,\dots, 2^k - 1}$ is $1$ exactly half of the time.

Edit: Based on Ross Millikan's comment, it is possible to express this as a sum over the bits which are $1$ in $n$, if they are ordered correctly. If ${a_1, a_2,\dots,a_m}$ are the exponents corresponding to the bits which are $1$ in $n$, ordered in increasing order, then $$F(n) = \sum_{i=1}^m a_i\,2^{a_i-1}-i\,2^{a_i}+n+1 = m(n+1) + \sum_{i=1}^m a_i\,2^{a_i-1}-i\,2^{a_i}$$
