Summation identity proof

**cubs3205** · October 10th 2009, 05:26 PM

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

**Laurent** · October 11th 2009, 01:38 AM

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.

Thread: Summation identity proof

LinkBack

Thread Tools

Display

Summation identity proof

Similar Math Help Forum Discussions

proof of summation

Summation identity

Cosine Summation Identity

Summation proof

summation identity proof

Search Tags