Proving $\sum_{k=1}^n\binom{n}kk=n\,2^{n-1}$

Question

Prove that, for all integers $k \geq 1$ and $n \geq k$, we have

$$\sum_{k=1}^n\binom{n}kk=n\,2^{n-1}$$

Would this involve differentiation by bringing the $n-1$ down? I tried to do that along with using the binomial theorem but couldn't quite get the answer on the right. This may be cause I was also confused on how to properly expand out $\binom{n}k$.

Any help?

Answer 1

To do it "by hand" by expanding the binomial factor: $$\begin{align} &\sum_{k=1}^{n}\binom{n}{k}k \\= &\sum_{k=1}^{n}\frac{n!}{k!(n-k)!}k \\= &\;n\sum_{k=1}^{n}\frac{(n-1)!}{(k-1)!(n-k)!} \end{align}$$ Then shift your indices carefully! $$\begin{align} = &\;n\sum_{k=0}^{n-1}\frac{(n-1)!}{k!(n-(k+1))!} \\= &\;n\sum_{k=0}^{n-1}\frac{(n-1)!}{k!((n-1)-k)!} \\= &\;n\sum_{k=0}^{n-1}\binom{n-1}{k} \\= &\;n2^{n-1} \end{align}$$

Answer 2

Your idea of differentiation can work, yes. We have

$$(x+y)^n=\sum_{k=0}^n\binom{n}kx^ky^{n-k}$$

Differentiating both sides with respect to $x$ yields:

$$n\,(x+y)^{n-1}=\sum_{k=1}^n\binom{n}kkx^{k-1}y^{n-k}$$

$($the term for $k=0$ is independent of $x$ and hence vanishes$)$. The proof follows from setting $x=y=1$ in the equation above.

Answer 3

Here is a combinatorial proof of this identity.

Imagine a group of $n$ people. You are to elect a head for this group, and then create a committee(of any size, even zero) from the remaining people.

In how many ways can this be done? One is this : choose the head in $n$ ways, and then choose a subset of the remaining $n-1$ people to form the committee. This is done in $2^{n-1}$ ways, since there are $2^{n-1}$ possible subsets. So one answer would be $n2^{n-1}$.

The other way would be this. Let's fix the number of people in the committee first. Call this number $n-k$. Clearly, $k = 0$ is not possible, since at least the head is not in the committee. Now, once this is done, pick the committee in $\binom {n}{n-k} = \binom{n}{k}$ ways. Then, a head must be one of the $k$ people left. So, for each $k$, the number of ways of doing things is $k \binom nk$. We sum from $k=1$ to $n$, and then get $\sum_{k=1}^n k \binom nk$.

But then, we are counting the same thing in two different ways. Hence, the answer follows i.e. $\sum_{k=1}^n k \binom nk = n2^{n-1}$.

Answer 4

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

$f'(x)=$

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

$x=1:$

$n2^{n-1}= \sum_{k=1}^{k=n}\binom{n}{k}k.$