# Proof of binomial sums

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

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

I considered $(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? $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$

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

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

$=\binom{n}{k} + \binom{n}{k-1} + \binom{n}{k-1} + \binom{n}{(k-1)-1}$
$=\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
$\binom{m+n}{k} = \sum_{i=0}^{k}\binom{m}{i} \binom{n}{k-i}$

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

$(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:
$\binom{m+n}{k} = \sum_{i=0}^{k}\binom{m}{i} \binom{n}{k-i}$
for $m, n \geq 0$ and $\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 $0\le k\le\min\{m,n\}$

We can do a combinational proof.
$\binom{m+n}{k}$ is the number of ways to choose k items from m+n.
If $0\le j\le k$ then $\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
$\binom{m+n}{k} = \sum_{i=0}^{k}\binom{m}{i} \binom{n}{k-i}$.