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.