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

Solution 1:

Take the binomial expansion of $(1+x)^n$. Differentiate both sides with respect to $x$, then substitute $x=1$ and that will give you the identity.

Solution 2:

Use Gauss' trick for summing a sequence: Combine the sum term-by-term with its reversed-order self, noting that the binomial coefficients are symmetric.

$$S = \sum_{r=0}^n r { n \choose r } = \sum_{r=0}^n (n-r) {n \choose n-r }$$

So,

$$\begin{eqnarray} 2 S &=& \sum_{r=0}^n \left( r {n\choose r} + (n-r) {n \choose n-r} \right)\\\\ &=& \sum_{r=0}^n \left( r {n\choose r} + (n-r) {n \choose r} \right)\\\\ &=& \sum_{r=0}^n \left( n {n\choose r} \right)\\\\ &=& n \sum_{r=0}^n {n\choose r}\\\\ &=& n 2^n \hspace{0.1in} \text{, by familiar identity} \end{eqnarray}$$

To use a specific example, say, $n= 4$. The "trick" is deal to add the sum to its reverse, so let's look at those sums ...

$$\begin{align} \sum_{r=0}^4 r\binom{4}{r} &\quad=\quad 0 \binom{4}{0} + 1 \binom{4}{1} + 2 \binom{4}{2} + 3\binom{4}{3} + 4\binom{4}{4} \quad= S \\ \sum_{r=0}^4(4-r)\binom{4}{4-r} &\quad=\quad 4 \binom{4}{4} + 3 \binom{4}{3} + 2 \binom{4}{2} + 1 \binom{4}{1} + 0\binom{4}{0} \quad= S \end{align}$$

The fact that the binomial coefficients are "symmetric" says that each such coefficient in the first sum matches the one below it in the second sum. Adding the sums "vertically" (that is, term-by-term), we have $$\sum_{r=0}^4 \left( r + (4-r) \right) \binom{4}{r} \quad=\quad 4\binom{4}{0} + 4\binom{4}{1} + 4\binom{4}{2} + 4\binom{4}{3} + 4\binom{4}{4} \quad=\quad 2 S$$ The trick has given us a common multiplier ($4$, which is to say $n$) that we factor-out: $$n \sum_{r=0}^4 \binom{4}{r} \quad=\quad 4\left(\;\binom{4}{0} + \binom{4}{1} + \binom{4}{2} + \binom{4}{3} + \binom{4}{4} \;\right) \quad=\quad 2 S$$ Finally, because we know the sum of binomial coefficients is an appropriate power of $2$ (why?), this gives $$4\cdot 2^4 = 2 S \qquad\to\qquad S = 4\cdot 2^3 = n\cdot 2^{n-1}$$

Solution 3:

Here's a hint:

$$r\binom{n}{r} = n\binom{n-1}{r-1}, \quad r\geq 1$$

Here be spoilers:

\begin{align} \sum_{r=0}^{n} r\binom{n}{r} &= \sum_{r=1}^{n} r\binom{n}{r} & &\text{drop the zero term} \\ &= \sum_{r=1}^{n} n\binom{n-1}{r-1} & &\text{apply the above identity} \\ &= n \sum_{k=0}^{n-1} \binom{n-1}{k} & &\text{replace index $r$ with $k=r-1$} \\ &= n 2^{n-1} & &\text{the sum is just the total number of subsets of $n-1$ elements} \end{align}

Solution 4:

I can't resist giving the standard bijective proof of this fact. Let $[n]$ be the set of integers from $1$ to $n$. Then $r {n \choose r}$ is the number of elements in all the subsets of $[n]$ which have $r$ elements. So your sum is the number of elements in all the subsets of $[n]$.

But we can pair the sets up into $2^{n-1}$ pairs of the form $S, [n] \setminus S$. Each pair contains $n$ elements, so all the sets together contain $n 2^{n-1}$ elements.