Proof of binomial sums

**CuriosityCabinet** · November 8th 2011, 04:35 AM

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

**seld** · November 8th 2011, 04:49 AM

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.

**veileen** · November 8th 2011, 04:54 AM

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

**Plato** · November 8th 2011, 07:01 AM

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

Thread: Proof of binomial sums

LinkBack

Thread Tools

Display

Proof of binomial sums

Re: Proof of binomial sums

Re: Proof of binomial sums

Re: Proof of binomial sums

Similar Math Help Forum Discussions

marginal moment for random sums - question about proof

An Equality of Binomial Sums

squaring sums, expand the given binomial sum.

Sums of Binomial Coefficients - proof by induction

Induction proof involving sums of consecutive powers

Search Tags