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

Question

I am trying to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$ but am not able to think something except induction,which is of-course not necessary (I think) here, so I am inquisitive to prove this in a more general way.

The left side of an identity occurs while solving another problem (concerning binomial theorem) so I am more interested in deriving the right side from the left side, else I have to remember it now onward.

EDIT: I am more interested in an algebraic proof rather than combinatorial argument or something involving calculus (however I liked svenkatr and Bill Dubuque solution), hence I am removing the combinatorics tag.

Answer 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.

Answer 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}$$

Answer 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}

Answer 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.

Answer 5

Here's a dirty trick. $\frac{1}{2^n} \sum_{r \ge 0} r {n \choose r}$ is the expected size of a random subset of an $n$-element set. But by linearity of expectation, this is $n$ times the probability that any given element is in a subset, which is $\frac{1}{2}$. So

$$\frac{1}{2^n} \sum_{r \ge 0} r {n \choose r} = \frac{n}{2}.$$

Edit: And as long as I have this written up somewhere, I might as well use it. In this math.SE answer I prove the following. If $a_n, b_n$ are sequences satisfying $b_n = \sum_{k=0}^n {n \choose k} a_k$, and if $A(x) = \sum_{n \ge 0} a_n x^n, B(x) = \sum_{n \ge 0} b_n x^n$, then

$$B(x) = \frac{1}{1 - x} A \left( \frac{x}{1 - x} \right).$$

In this example $a_n = n$. One can prove by various arguments that in this case $A(x) = \frac{x}{(1 - x)^2}$; this is a special case of an identity I use in the above answer. It follows that

$$B(x) = \frac{1}{1 - x} \left( \frac{ \frac{x}{1-x} }{ \left( 1 - \frac{x}{1-x} \right)^2 } \right) = \frac{x}{(1 - 2x)^2} = \frac{1}{2} \frac{2x}{(1 - 2x)^2} = \frac{1}{2} \sum_{n \ge 0} n \cdot 2^n x^n$$

as desired.

Answer 6

Another way is to consider the following arrangement with $n$ rows and $n+1$ columns

$\begin{pmatrix} {n \choose 0} & {n \choose 1} & \dots & {n \choose n} \\\\ {n \choose 0} & {n \choose 1} & \dots & {n \choose n} \\\\ \vdots & \vdots & \dots & \vdots \\\\ {n \choose 0} & {n \choose 1} & \dots & {n \choose n} \\\\ \end{pmatrix}$

What we want is the sum of the last $n$ elements of row 1, plus the sum of last $n-1$ elements of row 2 etc.

Which is same as the sum of the first $n$ elements of row $n$, plus the sum of the first $n-1$ elements of row $n-1$ etc, as ${n \choose r} = {n \choose n-r}$.

Thus the required sum is half the sum of all elements, which is $n2^{n-1}$, as the sum of each row is $2^n$ and there are $n$ rows.

---

Edit not by OP: I thought to add that this $n \times n + 1$ can also be construed by its columns.

$\sum_{r=0}^n {r {n \choose r}} = 0 + \color{green}{1\dbinom{n}{1}} + \color{purple}{2\dbinom{n}{2}} + ... + \color{#0073CF}{(n - 1)\binom{n}{n - 1}} + \color{olive}{n\binom{n}{n}} $

$\begin{pmatrix} {n \choose 0} & \color{green}{\binom{n}{1}} & \color{purple}{\binom{n}{2}} & \dots & & \color{#0073CF}{\binom{n}{n - 1}} & \color{olive}{\binom{n}{n}} \\\\ {n \choose 0} & {n \choose 1} & \color{purple}{\binom{n}{2}} & \dots & & \color{#0073CF}{\binom{n}{n - 1}} & \color{olive}{\binom{n}{n}} \\\\ \vdots & \vdots & \dots & \vdots \\\\ {n \choose 0} & {n \choose 1} & {n \choose 2} & \dots & & \color{#0073CF}{\binom{n}{n - 1}} & \color{olive}{\binom{n}{n}} \\\\ {n \choose 0} & {n \choose 1} & {n \choose 2} & \dots & & {n \choose n - 1} & \color{olive}{\binom{n}{n}} \\\\ \end{pmatrix}$

Answer 7

There are already some good answers here, but you did say that you wanted something general, so I'll add the following.

Suppose you are interested, for some function $f(k)$, in the binomial sum

$$B(n) = \sum_{k=0}^n \binom{n}{k} f(k).$$

(Your problem has $f(k) = k$.) Then, taking $\Delta f(k) = f(k+1) - f(k)$, denote $A(n)$ by

$$A(n) = \sum_{k=0}^n \binom{n}{k} \Delta f(k).$$

A few years ago I proved the following relationship between $B(n)$ and $A(n)$:

$$B(n) = 2^n \left(f(0) + \sum_{k=1}^n \frac{A(k-1)}{2^k}\right).$$

For your problem, $f(k) = k$. So $\Delta f(k) = k+1 - k = 1$. If you're willing to take

$$A(n) = \sum_{k=0}^n \binom{n}{k} = 2^n,$$

then the formula gives

$$\sum_{k=0}^n \binom{n}{k} k = 2^n \sum_{k=1}^n \frac{2^{k-1}}{2^k} = 2^n \sum_{k=1}^n \frac{1}{2} = n 2^{n-1}.$$

(Even if you're not willing to take $\sum_{k=0}^n \binom{n}{k} = 2^n,$ you can derive that immediately from the expression for $B(n)$ by letting $f(k) = 1$, as $\Delta f(k) = 0$ in that case.)

The expression for $B(n)$ is Theorem 4 in my paper "Combinatorial Sums and Finite Differences," Discrete Mathematics, 307 (24): 3130-3146, 2007. This identity is in the paper as well, as an illustration of Theorem 4.

Answer 8

HINT $\ $ Differentiate $\rm (1+x)^n\:$, use the binomial theorem, then set $\rm\ x = 1\:$.

NOTE $\ $ Using derivatives, we can pull out of a sum any polynomial function of the index variable, namely

since we have $\rm\:\ k^i\ x^k\ =\ (xD)^i \ x^k\ \ $ for $\rm\ \ D = \frac{d}{dx},\ \ k > 0\ $

it follows that $\rm\ \sum a_k\: f(k)\: x^k\ =\ f(x\:D) \sum a_k\: x^k\ \ $ for polynomial $\rm\:f\:$

The "trick" of representing a numerical series as the value f(1) of a generating function f(x) goes back at least to Euler, who employed it to sum divergent series (among other applications). The power arises from the fact that at the function level one has available much more powerful tools, esp. derivatives, e.g. above. Such techniques come in quite handy when shifting between differential and difference (recurrence) viewpoints, e.g. for hypergeometric functions and their special values.

Answer 9

Count all pairs $(x,S)$ where $S \subseteq \{1,2,\dots,n\}$ and $x \in S$ in two ways. Having chosen a $S$ to be an r-element subset, we have $r$ choices for $x$, giving us the left hand side, $\sum_{r \geq 1} r {n \choose r}$. Next having chosen an arbitrary element $x \in \{1,2,\dots,n\}$ we can choose $S$ in $2^{n-1}$ ways, and $x$ can be chosen in $n$ ways giving us the right hand side.

Answer 10

We have $x^{n} = (1+(x-1))^{n}$ and $$[1+(x-1)]^{n} = {n \choose 0 } + {n \choose 1} \cdot (x-1) + {n \choose 2} \cdot (x-1)^{2} + \cdots + {n \choose n} \cdot (x-1)^{n}$$

Differentiate on both sides w.r.t x and substitute the value $x=2$ in your equation.