1. Summation identity proof

I am having trouble proving this identity:

$\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.

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

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

$\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).
$m\choose n$ is the number of subsets of $\{1,\ldots m\}$ with $n$ elements.
$n\choose k$ is the number of subsets of $\{1,\ldots n\}$ with $k$ elements.
$m-n\choose n-k$ is the number of subsets of $\{n+1,\ldots m\}$ with $n-k$ elements.

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