Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 soution),hence I am removing the combinatorics tag.

share|improve this question
3  
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
add comment

10 Answers

up vote 19 down vote accepted

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.

share|improve this answer
3  
+1 ,Ingenious ;) –  Quixotic Oct 25 '10 at 3:04
8  
@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
4  
@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
show 1 more comment

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

share|improve this answer
8  
Tidy and calculus-free. +1! –  J. M. Oct 25 '10 at 4:47
add comment

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}

share|improve this answer
    
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
1  
@Debanjan: I've expanded my answer, hope this helps. –  Marcus Fry Oct 26 '10 at 6:06
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
1  
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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