I was asked to give a combinatorial proof of the following fact:
$$\forall n\in \mathbb N,\sum_{k=1}^n k\binom{n}{k} = n\times2^{n-1}$$
This seems somewhat simplistic to do via noting that the binomial theorem is: $$(1+x)^n=\sum_{k=1}^n\binom{n}{k}x^k$$ Then we can take the derivative and set x=1 to get our result above.
However, this is not via combinatorics and relies on algebra instead. How would you approach this combinatorially? I'm not sure where even to start.
How many ways are there from a group of $n$ people to fix a committee of arbitrary size and elect its head?
Overall count - pick the head in $n$ ways, and the rest $n-1$ can participate or be excluded, 2 choices for $n-1$ people, a grand total of $n2^{n-1}$ ways.
Alternatively, for a committee of size $k$, pick $k$ people in $\binom{n}{k}$ ways and fix the head in $k$ ways...