Chapter 1, Problem 1.14TE

From a set of n people, a committee of size j is to be chosen, and from this committee, a subcommittee of size $i,i\le j$, is also to be chosen.

a. Derive a combinational identity by computing, in two ways, the number of possible choices of the committee and subcommittee—first by supposing that the committee is chosen first and then the subcommittee is chosen, and second by supposing that the subcommittee is chosen first and then the remaining members of the committee are chosen.

b. Use part (a) to prove the following combinatorial identity: ${\displaystyle \underset{j=1}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right)}=\left(\begin{array}{c}n\\ i\end{array}\right)2^{n-i}i\le n$

c. Use part (a) and Theoretical Exercise 13 to show that ${\displaystyle \underset{j=1}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}j\\ i\end{array}\right)}{\left(-1\right)}^{n-j}=0i<n$