Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

marked as duplicate by Martin Sleziak, Sami Ben Romdhane, mookid, user127.0.0.1, Sanath K. Devalapurkar Mar 30 '14 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… and other posts, which are linked there. – Martin Sleziak Mar 30 '14 at 16:43

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|cite|improve this answer


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|cite|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|cite|improve this answer

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