I saw one proof using this formula: $$ \sum_{i=0}^{z} {n_1 \choose i}{n_2 \choose z-i} = {n_1+n_2 \choose z}$$ Can anyone help explain it, thank you!
$\begingroup$
$\endgroup$
1
-
$\begingroup$ See math.stackexchange.com/questions/337923/… and other posts, which are linked there. $\endgroup$– Martin SleziakCommented Mar 30, 2014 at 16:43
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
A subcommittee of $z$ members will be chosen from a committee consisting of $n_1$ Democrats and $n_2$ Republicans. The number of ways to choose $i$ Democrats and $z-i$ Republicans is $\dbinom{n_1}{i}\dbinom{n_2}{z-i}$. So the total number of ways to choose members of the subcommittee is the expression on the left. But it's also the expression on the right.
This is "Vandermonde's identity" (Google it).
$\begingroup$
$\endgroup$
$$\left(1+\binom{n_1}{1}x+\binom{n_1}{2}x^2+\cdots\right)=(1+x)^{n_1}$$
Obviously. And same for $n_2$.
Multiply these two equations, we get,
$$(1+x)^{n_1+n_2} = \left(1+\binom{n_1}{1}x+\binom{n_1}{2}x^2+\cdots\right)\left(1+\binom{n_2}{1}x+\binom{n_2}{2}x^2+\cdots\right)$$
Your given summation is the coefficient of $x^z$ in the RHS. That is equal to $\binom{n_1+n_2}{z}$ by the Binomial Theorem.
$\begingroup$
$\endgroup$
This is the Vandermonde identity. Choosing $z$ elements from a total of $n_1+n_2$, you must choose some number $i$ with $0\leq i\leq z$ from the first $n$, and the remaining $z-i$ from the last $n_2$. Whence the formula.
answered Mar 30, 2014 at 14:11