Sum of numbers less than $2^n$ with $m$ ones.

Question

My friend gave me a formula to calculate the sum of numbers with exactly $m$ ones in their binary representation that are less than $2^n$. It is as follows:

$$ {{n-1} \choose {m-1} }* (2^n-1)$$

Is this formula correct? If it is, could you kindly explain the logic behind it? Most probably, the $2^n-1$ comes from a geometric series, so, probably it has something to do with the distribution of the ones, I guess?...

Please help. Thank you.

Answer 1

A hint:

There are ${n\choose m}$ binary numbers having $n$ digits, among them exactly $m$ ones. Exactly ${1\over n}$ of all ones in the big list of these numbers are at the first, ${1\over n}$ at the second, $\ldots$, ${1\over n}$ at the $n^{\rm th}$ digit of the numbers.

Answer 2

Imagine to write down, row by row, each number in its binary representation, and put on top a row with the value $(2^0,2^1,\cdots)$ of each digit.

Now fix a digit (column): how many ones will be on it ? all the different ways in which you can distribute the remaining $m-1$ in the remaining $n-1$ digits. Then sum column by column, and you get the formula.