# Vandermonde identity

###### Theorem 1 ([1] 24.1.1 formula A. II.).

For any $p$ and $q$ and any $k$ with $\mathrm{0}\mathrm{\le}k\mathrm{\le}p\mathrm{+}q$,

$$\left(\genfrac{}{}{0pt}{}{p+q}{k}\right)=\sum _{i=0}^{k}\left(\genfrac{}{}{0pt}{}{p}{i}\right)\left(\genfrac{}{}{0pt}{}{q}{k-i}\right).$$ | (*) |

###### Proof.

Let $P$ and $Q$ be disjoint sets with $|P|=p$ and $|Q|=q$. Then the
left-hand side
of Equation (*) is equal to the number of subsets of $P\cup Q$ of size $k$.
To build a subset of $P\cup Q$ of size $k$, we first decide how many elements, say $i$ with $0\le i\le k$,
we will select from $P$. We can then select those elements in $\left(\genfrac{}{}{0pt}{}{p}{i}\right)$
ways. Once we have done so, we must select the
remaining $k-i$ elements from $Q$, which we can do in $\left(\genfrac{}{}{0pt}{}{q}{k-i}\right)$ ways. Thus there are $\left(\genfrac{}{}{0pt}{}{p}{i}\right)\left(\genfrac{}{}{0pt}{}{q}{k-i}\right)$ ways to select a subset of $P\cup Q$ of size $k$ subject to the restriction^{} that exactly $i$ elements come from $P$. Summing over all possible $i$ completes^{} the proof.
∎

## References

- 1 Abramowitz, M., and I. A. Stegun, eds. Handbook of Mathematical Functions. National Bureau of Standards, Dover, New York, 1974.

Title | Vandermonde identity^{} |
---|---|

Canonical name | VandermondeIdentity |

Date of creation | 2013-03-22 14:08:49 |

Last modified on | 2013-03-22 14:08:49 |

Owner | mps (409) |

Last modified by | mps (409) |

Numerical id | 8 |

Author | mps (409) |

Entry type | Theorem |

Classification | msc 05A19 |

Related topic | PascalsRule |