# 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 $$\displaystyle\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. Commented Oct 25, 2010 at 4: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}$$

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

• Tidy and calculus-free. +1! Commented Oct 25, 2010 at 4:47
• @Blue could you please go through this solution in more detail as it just happens to be almost exactly the same as my question? I don't really understand how you got to the answer. math.stackexchange.com/questions/1924680/… Commented Sep 13, 2016 at 9:01
• @differentialequation: I've added a walk-through of a specific example (six years later!).
– Blue
Commented Sep 13, 2016 at 10:15
• Isn't the answer to your original proof n2^n-1? Commented Sep 13, 2016 at 10:49
• @differentialequation: I don't understand your question. I mean, yes ... The symbolic proof does show that $S = n\cdot 2^{n-1}$. But the specific numerical example (with $n=4$) shows that $S = 4\cdot 2^{4-1}$, which is exactly consistent. Where's the confusion?
– Blue
Commented Sep 13, 2016 at 11:57

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.

• @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!) Commented Oct 25, 2010 at 4:46
• @Pete L. Clark: Do you mean this book : math.upenn.edu/~wilf/gfology2.pdf ? Commented Oct 25, 2010 at 8:17
• @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".) Commented Oct 25, 2010 at 13:53
• It's not a "trick" at all once you understand the combinatorial definition of differentiation and prove combinatorially that it satisfies the Leibniz rule. Then this proof becomes the decategorification of Michael Lugo's answer. Commented Oct 26, 2010 at 20:14
• Just wondering, why would you sub in x=1? Commented Sep 13, 2016 at 8:51

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 ? Commented Oct 25, 2010 at 8:29
• @Debanjan: apply this identity to every term and factor out n. Commented Oct 25, 2010 at 13:11
• @Debanjan: I've expanded my answer, hope this helps. Commented Oct 26, 2010 at 6:06
• Sorry to bring this up from a long time, ago, but what do you mean by the 'replace the index' section? Commented Sep 14, 2016 at 12:50
• @user193203821309 by "replace the index", we are changing the index in the summation. This step is purely notational, but can often be useful with seeing where to go next or simplifying the algebra. Note that you can always replace the index in any summation, but typically you want the index which makes the sum look easier. Commented Oct 27, 2017 at 23:45

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.

• (+1) This is the combinatorial interpretation of Blue's answer. Commented Nov 6, 2016 at 19:22

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. Commented Oct 26, 2010 at 14:59

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.

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). Commented Dec 6, 2010 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.

Aside from the many clever answers already given, one can do this as a plodding inductive argument as follows:

\begin{align} \sigma(n) &= \sum_{k=0}^n k\binom{n}{k}\\ &= \sum_{k=0}^n k\cdot{\bigg{[}\binom{n-1}{k-1}+\binom{n-1}{k}\bigg{]}}\\ &= \sum_{k=0}^{n-1}(k+1)\binom{n}{k}+\sum_{k=0}^{n-1}k\binom{n}{k}\\ &= 2\cdot\sigma(n-1)+2^{n-1}\\ \end{align}

So let's use this recursive formula to show that $$\sigma(n)=n\cdot2^{n-1}$$ by induction. Clearly, $$\sigma(1)=1$$. Assume $$\sigma(n-1)=(n-1)\cdot{2^{n-2}}$$ and let's show this gives the desired formula for $$\sigma(n)$$. From above, we have

$$\sigma(n)=2\cdot\sigma(n-1)+2^{n-1}=2(n-1)\cdot{2^{n-2}}+2^{n-1}=n\cdot{2^{n-1}}$$ as desired.

Even simpler, is just a direct calculation: $$\sum_{k=0}^n k\binom{n}{k}=\sum_{k=0}^n k\frac{n!}{k!(n-k)!}=\sum_{k=0}^n n\frac{(n-1)!}{(k-1)!(n-k)!}=\sum_{k=0}^{n-1} n\binom{n-1}{k}=n\cdot{2^{n-1}}$$

To prove the identity $$\sum_{r=0}^n r \binom{n}{r} = n \cdot 2^{n-1}$$ algebraically without using induction, let's proceed with a different approach.

Consider the binomial theorem, which states: $$(1+x)^n = \sum_{r=0}^n \binom{n}{r} x^r.$$

Differentiating both sides with respect to $$x$$: $$n(1+x)^{n-1} = \sum_{r=1}^n r \binom{n}{r} x^{r-1}.$$

Now, multiply both sides by $$x$$: $$nx(1+x)^{n-1} = \sum_{r=1}^n r \binom{n}{r} x^r.$$

Substitute $$x = 1$$ into the equation: $$n \cdot 2^{n-1} = \sum_{r=1}^n r \binom{n}{r} \cdot 1^r = \sum_{r=1}^n r \binom{n}{r}.$$

Therefore, $$\sum_{r=0}^n r \binom{n}{r} = n \cdot 2^{n-1}.$$

This completes the algebraic proof without using induction or combinatorial arguments. We leveraged the binomial theorem and differentiation to derive the desired identity directly.