# Binomial Expansion.

So I had a question: Prove that for $n \geq 1$, $${n \choose 1} + 2{n \choose 2} + 3{n \choose 3} + ...+ n{n \choose n} = n2^{n-1}$$

So my idea was to take the binomial expansion of $(1+1)^n$ which is clearly: $${n \choose 0} + {n \choose 1} + ... + {n \choose n}$$ by the binomial theorem.

So my idea was to multiply $(1 + 1)^n$ by $k$, so we have: $$k\sum_{k = 0}^n {n \choose k}(1)^{n-k}(1)^{k}$$

$$= \sum_{k = 0}^n k{n \choose k}(1)^{n-k}(1)^{k}$$

$$= {n \choose 1}+2{n \choose 2}+ ... + (n-1){n \choose n-1} + n {n \choose n}$$

I'm stuck here, I was thinking that: $${n \choose 1} + {n \choose 2} + ... + {n \choose n} = 2^{n-1}$$

but I fail to see how that's true, so any help would be nice! I feel like I'm close to my solution.

-
You can also turn the LHS around and add it to itself so all coefficients become n. (I'd post an answer, but I don't know LaTeX.) – user2357112 Apr 3 '14 at 1:11

Note that if $k\ne 0$, then $\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$, so $k\binom{n}{k}=n\binom{n-1}{k-1}$. Now you should be able to push the argument through.

Alternately, note that $(1+x)^n=\sum_0^n \binom{n}{k}x^k$. Differentiate with respect to $x$, and set $x=1$.

Another way: Imagine tossing a fair coin $n$ times. Then the mean number of heads is $$\sum_{k=1}^n k\binom{n}{k}\frac{1}{2^n}.$$ We will be finished if we can show that this mean is $\frac{n}{2}$.

Define the random variable $X_i$ to be $1$ if we have a head on the $i$-th toss and $0$ otherwise. Then the number of heads is $X_1+\cdots+X_n$. So the mean number of heads is $E(X_1)+\cdots+E(X_n)$. Each $X_i$ has mean $\frac{1}{2}$, so we are finished. I call this a mean proof.

-
Oh wow, I can't believe I didn't see this. Thanks! – Mark Apr 2 '14 at 20:19
You are welcome. – André Nicolas Apr 2 '14 at 20:24
A mean proof indeed. +pun – Omnomnomnom Apr 30 '14 at 1:11

Differentiate the following identity $\displaystyle(1+x)^n=\sum_{k=0}^n{n\choose k}x^n$ with regard to x, then let $x=1$.

-
Wow, this is clever. Although not the answer I'm looking for. :P – Mark Apr 2 '14 at 20:18