# Proof of binomial sums

• Nov 8th 2011, 04:35 AM
CuriosityCabinet
Proof of binomial sums
Prove:
$\displaystyle \binom{m+n}{k} = \sum_{i=0}^{k}\binom{m}{i} \binom{n}{k-i}$

for $\displaystyle m, n \geq 0$ and$\displaystyle 0 \leq k\leq m+n$.

I considered $\displaystyle (1+x)^m(1+x)^n$ but got stuck at manipulating double sums. Please help (Crying)
• Nov 8th 2011, 04:49 AM
seld
Re: Proof of binomial sums
Have you looked at this property? $\displaystyle \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$

So for example: $\displaystyle \binom{n+2}{k} =\binom{(n+2)-1}{k} + \binom{(n+2)-1}{k-1}$

$\displaystyle = \binom{n+1}{k} + \binom{n+1}{k-1}$

$\displaystyle =\binom{n}{k} + \binom{n}{k-1} + \binom{n}{k-1} + \binom{n}{(k-1)-1}$
$\displaystyle =\binom{n}{k} + 2\binom{n}{k-1} + \binom{n}{k-2}$

This may help a little.
• Nov 8th 2011, 04:54 AM
veileen
Re: Proof of binomial sums
$\displaystyle \binom{m+n}{k} = \sum_{i=0}^{k}\binom{m}{i} \binom{n}{k-i}$

The second sum is the coefficient of $\displaystyle x^{i+k-i}=x^{k}$ from $\displaystyle (1+x)^m \cdot (1+x)^n= (1+x)^{m+n}$.

$\displaystyle (1+x)^{m+n}=\sum_{k=0}^{m+n} \binom{m+n}{k} \cdot 1^{m+n-k} \cdot x^k=\sum_{k=0}^{m+n} \binom{m+n}{k} \cdot x^k$
• Nov 8th 2011, 07:01 AM
Plato
Re: Proof of binomial sums
Quote:

Originally Posted by CuriosityCabinet
Prove:
$\displaystyle \binom{m+n}{k} = \sum_{i=0}^{k}\binom{m}{i} \binom{n}{k-i}$
for $\displaystyle m, n \geq 0$ and$\displaystyle \color{red} 0 \leq k\leq m+n$.

FIRST, it must be pointed out that the is a mistake in the question.
This is Vandermonde's Theorem it should be $\displaystyle 0\le k\le\min\{m,n\}$

We can do a combinational proof.
$\displaystyle \binom{m+n}{k}$ is the number of ways to choose k items from m+n.
If $\displaystyle 0\le j\le k$ then $\displaystyle \binom{m}{j}\binom{n}{k-j}$ is the number of ways to choose those k items with j coming from the m group and k-j coming from the n group.
Now it us easy to see that
$\displaystyle \binom{m+n}{k} = \sum_{i=0}^{k}\binom{m}{i} \binom{n}{k-i}$.