17
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Isaac Oct 25 '10 at 4:53

10 Answers 10

34
$\begingroup$

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.

$\endgroup$
  • 9
    $\begingroup$ @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!) $\endgroup$ – Pete L. Clark Oct 25 '10 at 4:46
  • 1
    $\begingroup$ @Pete L. Clark: Do you mean this book : math.upenn.edu/~wilf/gfology2.pdf ? $\endgroup$ – Quixotic Oct 25 '10 at 8:17
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Oct 25 '10 at 12:57
  • 6
    $\begingroup$ @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".) $\endgroup$ – Pete L. Clark Oct 25 '10 at 13:53
  • $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Oct 26 '10 at 20:14
32
$\begingroup$

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

$\endgroup$
  • 8
    $\begingroup$ Tidy and calculus-free. +1! $\endgroup$ – J. M. is a poor mathematician Oct 25 '10 at 4:47
  • $\begingroup$ @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/… $\endgroup$ – user193203821309 Sep 13 '16 at 9:01
  • 1
    $\begingroup$ @differentialequation: I've added a walk-through of a specific example (six years later!). $\endgroup$ – Blue Sep 13 '16 at 10:15
  • 1
    $\begingroup$ Isn't the answer to your original proof n2^n-1? $\endgroup$ – user193203821309 Sep 13 '16 at 10:49
  • $\begingroup$ @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? $\endgroup$ – Blue Sep 13 '16 at 11:57
24
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ I didn't much understood what is hinted here, could you please explain a bit ? $\endgroup$ – Quixotic Oct 25 '10 at 8:29
  • $\begingroup$ @Debanjan: apply this identity to every term and factor out n. $\endgroup$ – Qiaochu Yuan Oct 25 '10 at 13:11
  • 2
    $\begingroup$ @Debanjan: I've expanded my answer, hope this helps. $\endgroup$ – Marcus Fry Oct 26 '10 at 6:06
  • $\begingroup$ Sorry to bring this up from a long time, ago, but what do you mean by the 'replace the index' section? $\endgroup$ – user193203821309 Sep 14 '16 at 12:50
  • $\begingroup$ @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. $\endgroup$ – mdave16 Oct 27 '17 at 23:45
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (+1) This is the combinatorial interpretation of Blue's answer. $\endgroup$ – wchargin Nov 6 '16 at 19:22
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Qiaochu Yuan Oct 26 '10 at 14:59
8
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Nate Eldredge Dec 6 '10 at 22:22
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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