Summation identity proof

• Oct 10th 2009, 05:26 PM
cubs3205
Summation identity proof
I am having trouble proving this identity:

$\displaystyle \sum_{k=0}^n$ $\displaystyle n \choose k$ $\displaystyle m - n \choose n - k$ = $\displaystyle m \choose n$

It gives a hint that you should try to interpret each of the summands.

I can't seem to use induction because there are factorials involved. And the summands don't have items that cancel out. It does seem related to a hypergeometric distribution however.

Thanks :)
• Oct 11th 2009, 01:38 AM
Laurent
Quote:

Originally Posted by cubs3205
I am having trouble proving this identity:

$\displaystyle \sum_{k=0}^n{n \choose k}{m - n \choose n - k} = {m \choose n}$

It gives a hint that you should try to interpret each of the summands.

Here's the idea for a combinatorial proof (it seems to be the one the hint suggests).
$\displaystyle m\choose n$ is the number of subsets of $\displaystyle \{1,\ldots m\}$ with $\displaystyle n$ elements.
$\displaystyle n\choose k$ is the number of subsets of $\displaystyle \{1,\ldots n\}$ with $\displaystyle k$ elements.
$\displaystyle m-n\choose n-k$ is the number of subsets of $\displaystyle \{n+1,\ldots m\}$ with $\displaystyle n-k$ elements.

Do you get it? Any $\displaystyle n$-element subset of $\displaystyle \{1,\ldots,m\}$ provides both a $\displaystyle k$-element subset of $\displaystyle \{1,\ldots,n\}$ and an $\displaystyle (n-k)$-element subset of $\displaystyle \{n+1,\ldots,m\}$, where $\displaystyle k\in\{1,\ldots,n\}$. And vice-versa. And this is what the equality says.