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.
Best Answer
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.