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

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.

-
I think if you combine Marcus Fry's hint with the fact that $\sum_{k=0}^m{m\choose k}=2^{m}$, you'll have an algebraic proof. – Isaac Oct 25 '10 at 4:53

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.

-
+1 ,Ingenious ;) – Quixotic Oct 25 '10 at 3:04
@Debanjan: please don't take the following sentence the wrong way. This is not ingenious: it's a standard trick, perhaps "page 3" in the playbook of formal power series manipulations. (Now I expect someone to check Generatingfunctionology and tell me the exact page number on which this trick appears!) – Pete L. Clark Oct 25 '10 at 4:46
@Pete L. Clark: Do you mean this book : math.upenn.edu/~wilf/gfology2.pdf ? – Quixotic Oct 25 '10 at 8:17
This "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 more powerful tools, esp. derivatives, e.g. see my answer for how derivatives permit one to pull out of a sum any polynomial function of the sum index variable. – Bill Dubuque Oct 25 '10 at 12:57
@Debanjan: yes, that's the book. (BTW, I agree with Bill Dubuque here. A "trick" which is several hundred years old, has innumerable applications, and is taught in courses would better be called a "technique".) – Pete L. Clark Oct 25 '10 at 13:53

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

-
Tidy and calculus-free. +1! – J. M. Oct 25 '10 at 4:47

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}

-
I didn't much understood what is hinted here, could you please explain a bit ? – Quixotic Oct 25 '10 at 8:29
@Debanjan: apply this identity to every term and factor out n. – Qiaochu Yuan Oct 25 '10 at 13:11
@Debanjan: I've expanded my answer, hope this helps. – Marcus Fry Oct 26 '10 at 6:06

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.

-

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

-

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.

-

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.

-
Of course, the expected size of a random subset is the same as the expected size of its complement, so that's another way to get the n/2 answer. This is a probabilistic version of Day Late Don's answer. – Qiaochu Yuan Oct 26 '10 at 14:59

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.

-

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.

-
A nice way to think about this: from a body of $n$ people, you wish to count the number of ways to select a committee of arbitrary size with a chairperson. On the left side, you perform the selection by choosing $r$ committee members (there are $\binom{n}{r}$ ways to do so) and then choosing one of the $r$ to be chair. On the right, you first select the chairperson ($n$ choices), and then for each remaining person, you decide whether or not they are assigned to the committee ($2^{n-1}$ choices). – Nate Eldredge Dec 6 '10 at 22:22

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.

-