0
$\begingroup$

I'm trying to prove that $\sum_{0\le i\le k} \binom{n}{i}.\binom{m}{k-i} = \binom{m+n}{k}.$ I got the constants $m!$ and $n!$ out of the sum but I couldn't proceed.

  • 1
    Proof by induction works fine, too. I had to prove this, too. But the algebraic proof on the wikipedia page wasnt my favorite.2012-10-25

3 Answers 3

5

To select $k$ peaces of fruit from $m$ apples and $n$ pears, you can also first select a number $0\le i\le k$ of apples you want, select $i$ aplles and $k-i$ pears.

2

Notice that $\binom{m+n}{k}$ is the number of ways of choose $k$ elements between $m+n$ given elements. Then you can think these $m+n$ elements separated in two blocks of $m$ and $n$ elements. So, if you choose
$i$ elements in the block of the $n$ elements and $k-i$ in the block of the $m$ elements, you choose $k$ elements between the $m+n$ given elements.

1

How can you chose $k$ objects from $m+n$?

You chose some ($i$) from the first $m$ and then chose $k-i$ from the second. And $0 \leq i \leq k$...