14. 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* ≤ *j*, is also to be chosen.

(a) Derive a combinatorial identity by computing, in two ways, the number of possible choices of the committee and subcommittee—first by suppos-

ing that the committee is chosen first and then the subcommittee, 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:

$$

\sum_{i=1}^{n} {n \choose i} {i \choose j} = {n \choose j} 2^{n-i}

$$

*i* ≤ *n*

(c) Use part

(a) and Theoretical Exercise 13 to show that

$$

\sum_{i=1}^{n} {n \choose i} {i \choose j} (-1)^{n-i} = 0

$$

*i* ≤ *n*