12. Consider the following combinatorial identity:

$$

\sum_{k=1}^{n} \binom{n}{k} = n\cdot 2^{n-1} - 1

$$

(a) Present a combinatorial argument for the above by considering a set of n people and determining, in two ways, the number of possible selections of a committee of any size and a chairperson for the committee.

HINT: (i) How many possible selections are there of a committee of size k and its chairperson?

(ii) How many possible selections are there of a chairperson and the other committee members?

(b) Verify the following identity for n = 1, 2, 3, 4, 5:

$$

\sum_{k=1}^{n} \binom{n}{k}^2 = 2^{n-2}n(n+1)

$$

For a combinatorial proof of the above, consider a set of n people, and argue that both sides of the identity above represent the number of different selections of a committee, its chairperson, and its secretary (possibly the same as the chairperson).

HINT:

(i) How many different selections result in the committee con-

taining exactly k people?

(ii) How many different selections are there in which the chair-

person and the secretary are the same?

(ANSWER: n2^n-1.)

(iii) How many different selections result in the chairperson and the secretary being different?

(c) Now argue that