# Counting arguments Given one prove the other identity

Given: $${n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n} = 2^n$$

Prove the following in 2 ways.

$${n \choose 1} + 2 {n \choose 2} + 3 {n \choose 3} + \cdots + n{n\choose n} = n 2^{n-1}.$$

I have already figured out one:

$$\sum_0^n k\binom{n}{k}$$

Makes up part of the computation for the expected size of a group if you randomly select items from the total. This expected value is half of the size of the total. Thus:

$$\frac{\sum_0^n k\binom{n}{k}}{\sum_0^n \binom{n}{k}} = \frac{n}{2}$$

With the result that $\sum_0^n\binom{n}{k} = 2^n$, this gives:

$$\sum_0^n k\binom{n}{k} = \frac{n}{2}2^n = n2^{n - 1}$$ Which then equals the RHS But I cannot figure out another way. Thanks for any help

• See this question. You can get this by differentiating the binomial theorem. – lulu Jun 4 '16 at 14:33
• @vadim123: Thank you for pointing this out, I thought that he wanted a proof for both expressions. – MrYouMath Jun 4 '16 at 14:41

$$\sum_{k=0}^n k\binom{n}{k} = \sum_{k=1}^n \frac{k n!}{k!(n-k)!} \\= \sum_1^n \frac{n!}{(k-1)!(n-k)!} \\ =n\sum_1^n \frac{(n-1)!}{(k-1)!(n-k)!} \\ =n\sum_0^{n-1} \frac{(n-1)!}{k!(n-1-k)!} \\ =n2^{n-1}$$

Second way can be done by blowing apart the binomials: $$\frac{k}{n}{n\choose k}=\frac{k}{n}\frac{n!}{(n-k)!k!}=\frac{(n-1)!}{(n-k)!(k-1)!}={n-1\choose k-1}$$ Now sum those up from $k=1$ to $k=n$ and you will get $2^{n-1}$.

Differentiating the binomial theorem is the "first way". OP's method is actually a third way, a nice combinatorial proof.

• Thank you very much, if you could, could you please explain the first way of differentiating the binomial theorem as I actually don't know how to do that. – user344569 Jun 4 '16 at 14:41
• See @david holden's solution for that method. – vadim123 Jun 4 '16 at 14:55

We are going to count the number of ways of making a team of any size less or equal to $n$ and then choose one as the leader of the team.

If the team is of size $k$ then the number of ways is $k{n\choose k}$. If the size of the team is not determined then we have $\sum_{k=1}^n k{n\choose k}$ ways.

The other counting is by first selecting the leader. Since there are $n$ people there are $n$ ways to select the leader. Then among the remaining $n-1$ people we can choose any subset of those $n-1$ people in $2^{n-1}$ ways to make a team. So in total we have $n\cdot 2^{n-1}$ ways.

Hint what's the derivative of original equation. Using derivatives can be one of the second way.

$$(1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k \\ n(1+x)^{n-1} = \sum_{k=1}^n k \binom{n}{k}x^{k -1}$$ set $x=1$