Is there a formula in permutations and combinations if we are to find the sum of number of 1's in binary expansion of a number from 1 to n We are given $N$. Suppose $f(x) =$ number of $1$'s in the binary expansion of $x$.
We have to calculate $f(1) +f(2) +f(3)+ \dots +f(N)$.
So is there a formula for this sum directly in terms of permutations and combinations?
Thanks in advance.
 A: If you calculate the first the desired values for $N=1,\dots,8$ and submit them to The On-Line Encyclopedia of Integer Sequences, the very first return is the one that you want: this sequence is OEIS A000788. No closed form is listed, but there is a nice recurrence. If $a_n=\sum_{k=0}^nf(k)$, then
$$\begin{align*}
a_0&=0\;,\\
a_{2n}&=a_n+a_{n-1}+n\;,\text{ and }\\
a_{2n+1}&=2a_n+n+1\;.
\end{align*}$$
To see why $a_{2n}=a_n+a_{n-1}+n$, note that $f(2k)=f(k)$ and $f(2k+1)=f(2k)+1=f(k)+1$ for all $k\in\Bbb N$. Thus,
$$\begin{align*}
a_{2n}&=\sum_{k=0}^{2n}f(k)\\
&=\sum_{k=0}^nf(2k)+\sum_{k=0}^{n-1}f(2k+1)\\
&=\sum_{k=0}^nf(k)+\sum_{k=0}^{n-1}\Big(f(k)+1\Big)\\\\
&=a_n+a_{n-1}+n\;.
\end{align*}$$
I’ll leave the recurrence for $a_{2n+1}$ to you; it can be verified similarly.
The OEIS entry gives a number of references and various formulas for $a_n$ involving summations, as well as a (moderately ugly) generating function.
A: It is not too hard to figure out (but a bit messy!) by noting that the 1's column switches between 0 and 1 for each number which gives the roof of N/2 1's, the 2's column switches between 0 and 1 every two numbers (think about how many 1's this gives), the 4's column switches between 0 and 1 every four numbers, etc.
