0
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ Thank you. This is clean, simple, and easy to understand. Exactly what I was looking for. $\endgroup$ – Mohammed Smithson Mar 29 '18 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.