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!

  • 1
    $\begingroup$ 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). $\endgroup$ – Mees de Vries Sep 6 '16 at 21:51
  • 2
    $\begingroup$ Technically, it is only true for $m>0$. This can be fixed by adding the $k=0$ term to the left side. $\endgroup$ – 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$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.