Combinatorial proofs
Proof 2
We can form a committee of size from a group of people in
ways. Now we hand out the numbers to of the people. We can then divide our committee-forming process into exhaustive and disjoint cases based on the committee member with the lowest number, . Note that there are only people without numbers, meaning we must choose at least one person with a number in order to form a committee of people. In general, in case , person is on the committee and persons are not on the committee. The rest of the committee can then be chosen in
ways. Now we can sum the values of these disjoint cases, and using double counting, we obtain