Trying to find $\sum\limits_{k=0}^n k \binom{n}{k}$ [duplicate]

\begin{align} &\sum_{k=0}^n k \binom{n}{k} =\\ &\sum_{k=0}^n k \frac{n!}{k!(n-k)!} =\\ &\sum_{k=0}^n k \frac{n(n-1)!}{(k-1)!((n-1)-(k-1))!} = \\ &n\sum_{k=0}^n \binom{n-1}{k-1} =\\ &n\sum_{k=0}^{n-1} \binom{n}{k} + n \binom{n-1}{-1} =\\ &n2^{n-1} + n \binom{n-1}{-1} \end{align}

1. Do I have any mistake?
2. How can I handle the last term?

(Presumptive) Source: Theoretical Exercise 1.12(a), P18, A First Course in Pr, 8th Ed, by S Ross

marked as duplicate by Mike Spivey, Henry T. Horton, TMM, hardmath, Stefan HansenJan 14 '13 at 19:12

• $\binom nr=0$ if $r<0$ or $r<n$ – lab bhattacharjee Jan 14 '13 at 15:21
• By convention $\binom{n}k=0$ if $k$ is a negative integer, so your last line is simply $$n\sum_{k=0}^n\binom{n-1}{k-1}=n\sum_{k=0}^{n-1}\binom{n}k=n2^{n-1}\;.$$ Everything else is fine. – Brian M. Scott Jan 14 '13 at 15:22
• Thank you, you should have put that as an answer – Bojan Serafimov Jan 14 '13 at 15:23
• Okay; I’ve made it an answer and added a longer comment that I didn’t make before. – Brian M. Scott Jan 14 '13 at 15:31
• Alternatively you could drop $k=0$ from the initial summation since its contribution is zero. – hardmath Jan 14 '13 at 15:42

By convention $\binom{n}k=0$ if $k$ is a negative integer, so your last line is simply $$n\sum_{k=0}^n\binom{n-1}{k-1}=n\sum_{k=0}^{n-1}\binom{n}k=n2^{n-1}\;.$$ Everything else is fine.

By the way, there is also a combinatorial way to see that $k\binom{n}k=n\binom{n-1}{k-1}$: the lefthand side counts the ways to choose a $k$-person committee from a group of $n$ people and then choose one of the $k$ to be chairman; the righthand side counts the number of ways to select a chairman ($n$) and then the other $k-1$ members of the committee.

If you know some elementary calculus, there's a simple way to do this.

By the Binomial theorem we have $$(x+1)^n=\sum_{k=0}^n \binom{n}{k}x^k$$ Differentiate both sides with respect to $x$: $$n(x+1)^{n-1}=\sum_{k=0}^n\binom{n}{k}kx^{k-1}$$ Set $x=1$ $$n2^{n-1}=\sum_{k=0}^n k\binom{n}{k}$$

• lol genious :DD – Bojan Serafimov Jan 14 '13 at 15:49

The annoying $\binom{n-1}{-1}$ at the end can be most easily avoided by starting with the observation that $$\sum_0^nk\binom{n}{k}=\sum_1^nk\binom{n}{k}.$$

Remark: For another way of summing the series, let $X$ be the number of tosses when a fair coin is tossed $n$ times. By symmetry we have $E(X)=n/2$. But $$E(X)=\sum_0^n k\binom{n}{k}\frac{1}{2^n}.$$ The result follows immediately. A mean proof!

• +1. André, I've seen you give or refer to mean proofs a few times. I really like them. Do you know of any references or collections of mean proofs? – Mike Spivey Jan 14 '13 at 20:46
• @MikeSpivey: It is a term I may have invented, in imitation of Proofs that Really Count. Do not know of any collection. – André Nicolas Jan 14 '13 at 20:52

As an completely different method to compute the sum (though that's not what was asked for): Note that the derivative of $$\sum_{k=0}^n {n\choose k}x^k=(1+x)^n$$ is $$\sum_{k=0}^n k {n\choose k}x^{k-1}=n(1+x)^{n-1}$$ and we want the value at $x=1$.