This is a question in my textbook that does not provide a solution. Any help on a solution?
Consider the following identity:
$\sum^{n}_{k=1} k\binom{n}{k} = n\cdot 2^{n-1}$
Present a combinatorial argument for the identity by considering a set of $n$ people and determining,in two methods, the number of ways you can select a committee of any size and a chair personfor the committee
(a) How many ways possible you can select a committee of size k and its chairperson?
(b) How many ways possible you can select a chairperson and the other committee members?
Best Answer
Okay. We can form a committee with a chairperson of size $k$ by first choosing $k$ people from our group of $n$, and from those $k$ people we may choose someone to chair the committee. There are $\binom{n}{k}$ ways to perform the first task, and $k$ ways to perform the second task, and so $k\binom{n}{k}$ ways to form a committee of size $k$ with a chairperson.
Summing over $1\le k\le n$, we have the number of ways to form a committee with a chairperson of size less than or equal to $n$ is precisely $\sum_{k=1}^{n}k\binom{n}{k}$.
You can also form a committee with a chairperson of size less than or equal to $n$ by choosing the chairperson first, then the rest of the committee. There are $n$ choices to choose the chairperson from. For the remaining $n-1$ people, the selector has two choices for each person: to include them or not. So we have $n$ choices for the chairperson, $2$ choices for the next, $2$ choices for the next, etc. Multiplying these together, we have $n2^{n-1}$ ways to form such a committee, which proves the identity.