Proving $ \sum _{k=0} ^m \binom nk \binom{n-k}{m-k} = 2^m \binom {n}{m}$.

Question

Give an algebraic and a combinatorial proof for the following identity:

$$ \sum _{k=0} ^m \binom nk \binom{n-k}{m-k} = 2^m \binom {n}{m}.$$

For the combinatorial argument, use the analogy of $n$ party guests, where $m$ of them describe themselves as either vegetarian or vegan (but not both).

After proving the identity using algebraic transformations, I'm unable to find a combinatorial argument for it. For the right hand side, if we multiply $\binom nm $ by $2^n$, we get the Pascal-triangle but with each row multiplied by $2^n$, but here we're multiplying by $2^m$. What does this mean? How does the analogy with the party guests work? Any help would be much appreciated.

Answer 1

It’s not the best analogy, since it requires us to assume that we can actually choose which guests are vegan and which are vegetarian, but I’ll go ahead and use it.

We can first choose $m$ guests to be the vegetarians and vegans; this can be done in $\binom{n}m$ ways. Once they are chosen, we can pick some subset of them to be the vegans; this can be done in $2^m$ ways, since there are $2^m$ subsets of an $m$-element set. Thus, the righthand side does indeed count the ways to choose $m$ of the guests and split them into vegans and vegetarians.

Alternatively, we could first choose $k$ guests to be vegan, where $0\le k\le m$, and then we could choose $m-k$ of the remaining $n-k$ guests to be vegetarians. Thus, there are $\binom{n}k\binom{n-k}{m-k}$ ways to choose $k$ vegans and $m-k$ vegetarians. If we sum over all values of $k$ from $0$ through $m$, this gives us every possible way of choosing $m$ guests and splitting them into vegans and vegetarians, so the lefthand side counts the same thing as the righthand side.

Answer 2

Choose $m$ people from a set of $n$ people and these $m$ people will be vegan or vegeterian This is the RHS.

Choose $\color{red}{k}$ people from $n$ and they will be vegan, now choose $\color{blue}{m-k}$ people from the remaining $n-k$ peoples they will be vegetarian Let $k$ range over $0$ to $m$. This is the LHS.

Answer 3

Straightforward calculation: $\binom{n}{k}\binom{n-k}{m-k}=\frac{n!(n-k)!}{k!(n-k)!(n-m)!(m-k)!}\times\frac{m!}{m!}=\binom{n}{m}\binom{m}{k}$

Now take the sum over $k$, i.e. $\sum_{k=0}^m\binom{m}{k}=2^m$.

Answer 4

To generate a party of $n$ where $m$ guests have binary preferences, you can:

1. Select $m$ guests first, and then choose a preference for every one of them.

2. Or you can choose how many vegetarians you have and assign them. After that assign to the non-vegetarian guests the left number of vegan options.