# By counting the same set in two different ways prove that $\Sigma_{k=1}^n$ ${k}\choose {m}$ ${n}\choose {k}$ = ${n}\choose {m}$ $2^{n-m}$

By counting the same set in two different ways (a combinatorial proof), prove that

$\Sigma_{k=1}^n$${k}\choose {m}$${n}\choose {k}$ = ${n}\choose {m}$$2^{n-m}$

I'm completely unsure about how to approach this problem. The above was all I was given but I'm unsure because I feel like $m$ is ambiguous and also what if $k$ is less than $m$.

Any advice or proofs appreciated!

• Usually when $k < m$ we say that $\binom{k}{m} = 0$ (namely, there are 0 ways to choose $m$ elements from a $k$ element set). – Mees de Vries Sep 6 '16 at 21:51
• Technically, it is only true for $m>0$. This can be fixed by adding the $k=0$ term to the left side. – Thomas Andrews Sep 6 '16 at 21:54

Suppose we want to choose 2 teams to play each other from a set of $n$ people,

where the first team has $m$ players.

1) On the right side, you are first selecting the players on the first team and then selecting some subset $\;\;\;$(possibly empty) of the remaining players as the second team.

2) On the left side, you are first selecting all the $k$ players, and then selecting the $m$ members of team 1 from $\;\;\;$among them.

(As Thomas Andrews points out, this is valid if $m>0$ for the formula as written.)

Here is a model for the counting:

RHS: Let there be $n$ boxes. In each box there is a white and a red ball. Now select $m$ of the boxes and pick precisely one ball from each of the remaining $n-m$ boxes.

LHS: Select first $k$ boxes among the $n$ and pick the red ball from the rest. Now select $m$ boxes among the $k$ and pick the white ball from the rest. (so in particular, $m\leq k \leq n$ and sum over $k$).