(Solved):
Consider the following combinatorial identity: k=1nk(nk)=n2n1. Gi ...
???????
Consider the following combinatorial identity: k=1?n?k(nk?)=n2n?1. Give a combinatorial proof as follows: consider the number of ways to form a committee with one person designated as chairperson from a set of n people, and count the number of possible selections in two ways: (a) [4 points] First, consider the number of committees of size k=1 with one person as chair. How many committees satisfying this criteria can be formed? (b) [4 points] How many committees of size k=2 can be formed with one person designated as chair? (c) [4 points] How many committees of size k can be formed with one person designated as chair?
(d) [4 points] If the size of the committee is not specified, how many total possible committees can be formed with one person designated as chair? How does this computation relate to the combinatorial identity? (e) [4 points] Now we compute the total committees obtained in parts (a)-(d) another way. Write down a different expression that computes the total number of committees of arbitrary size (up to the number of people n ) by first selecting the chairperson and then selecting the remaining members. How does this help us conclude the combinatorial identity?