Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

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!

share|improve this question

marked as duplicate by Martin Sleziak, Sami Ben Romdhane, mookid, user127.0.0.1, SDevalapurkar Mar 30 at 17:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
See math.stackexchange.com/questions/337923/… and other posts, which are linked there. –  Martin Sleziak Mar 30 at 16:43

3 Answers 3

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).

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.