Possible Duplicate:
How to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$?

$$\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 Hansen Jan 14 '13 at 19:12

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ $\binom nr=0$ if $r<0$ or $r<n$ $\endgroup$ – lab bhattacharjee Jan 14 '13 at 15:21
  • 1
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott Jan 14 '13 at 15:22
  • $\begingroup$ Thank you, you should have put that as an answer $\endgroup$ – Bojan Serafimov Jan 14 '13 at 15:23
  • $\begingroup$ Okay; I’ve made it an answer and added a longer comment that I didn’t make before. $\endgroup$ – Brian M. Scott Jan 14 '13 at 15:31
  • $\begingroup$ Alternatively you could drop $k=0$ from the initial summation since its contribution is zero. $\endgroup$ – 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} $$

  • $\begingroup$ lol genious :DD $\endgroup$ – 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!

  • $\begingroup$ +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? $\endgroup$ – Mike Spivey Jan 14 '13 at 20:46
  • $\begingroup$ @MikeSpivey: It is a term I may have invented, in imitation of Proofs that Really Count. Do not know of any collection. $\endgroup$ – 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$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.