Combinatorics proof of identity $\sum_{k=1}^{n}kC_n^k=n2^{n-1}$

Question

I'm having a great difficulty solving the revision question below for my test:

I have attempted the question as follows to get me started:
$(1+x)^n = \sum_{k=0}^n C_k^n, x\in R$
$\frac{d}{dx} (1+x)^n = n(1+x)^{n-1} = \sum_{k=0}^{n}C_k^nk x^{k-1} = \sum_{k=1}^{n}kC_k^n x^{k-1}$

From here, I have no idea how to proceed. Any help would be highly appreciated.

Answer 1

You will find many proofs there and among them 2 combinatorial proofs.

Remark: if it can help you for a subsequent web search, I just "googled" the key words "combinatorial proof $n 2^{n-1}$" and the second item I found (knowing the quality of "cut-the-knot" site, it's true) was a thorough one.

Answer 2

First argument:

There are $C_k^n$ ways to pick $k\ge1$ persons among $n$, and for every such committee $k$ possible chairmen.

With $n=3$: $a, b, c, ab, ac, bc, abc\to A; B; C; Ab, aB; Ac, aC; Bc, bC; Abc, aBc, abC$.

Second argument:

There are $n$ ways to elect a chairman among $n$, and $2^{n-1}$ ways to form a committee with the remaining $n-1$ persons.

With $n=3$: $A, B, C\to A, Ab, Ac, Abc; B, aB, Bc, aBc; C, aC, bC, abC$.

---

Note that committees of a single person (implicitly the chairman) are counted.