Vandermonde identity
Theorem 1 ([1] 24.1.1 formula A. II.).
For any and and any with ,
(*) |
Proof.
Let and be disjoint sets with and . Then the
left-hand side
of Equation (*) is equal to the number of subsets of of size .
To build a subset of of size , we first decide how many elements, say with ,
we will select from . We can then select those elements in
ways. Once we have done so, we must select the
remaining elements from , which we can do in ways. Thus there are ways to select a subset of of size subject to the restriction that exactly elements come from . Summing over all possible 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 |