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$
0

1 Answer 1

Reset to default
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$
1
  • $\begingroup$ Thank you. This is clean, simple, and easy to understand. Exactly what I was looking for. $\endgroup$
    – Mohammed Smithson
    Mar 29, 2018 at 18:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .