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 know that the expansion of $\sum \limits_{k = 0}^{n} (-1)^{k} \binom{n}{k}$ equals to zero. But why is $\sum \limits_{k = 0}^{n} (-1)^{k} k\binom{n}{k}$ also equal to zero for $n \geq 2$?

I've been using the first to derive the second, but it ended with no clue at all. Anyone know about how to derive this formula?

$$\displaystyle \sum_{k = 0}^{n} (-1)^{k} k\binom{n}{k} = 0 .$$

share|improve this question
add comment

4 Answers 4

up vote 14 down vote accepted

Note that $(1-x)^n = \sum_{k=0}^n (-1)^k x^k \binom{n}{k}$. Thus the sum you are interested in is $\left. \frac{\mathrm{d}}{\mathrm{d} x} (1-x)^n \right|_{x=1} = \left. -n (1-x)^{n-1} \right|_{x=1} = -n (1-1)^{n-1}$. Thus it is zero for $n > 1$.

Indeed for $n=1$ is the sum is $-1$, which can be explicitly checked.

share|improve this answer
add comment

I would like to give another different proof of the problem the OP proposed. My solution is based on the identity

$$k\binom{n}{k}=n\binom{n-1}{k-1}.$$

Let us first prove this identity: suppose we are given a class of $n$ children and suppose we want to form a team of $k$ people from the class, and moreover we want to elect a captain for our team. We can count the possibilities of doing so in two ways:

First select $k$ people from the class and then elect the captain. Then we have $k$ possibilities for any previously chosen team, so in total $$k\binom{n}{k}$$ ways of proceeding along this path.

But we may also elect first the captain, which can be done in $n$ ways, then form the team, for which we need other $k-1$ children out of $n-1$ remaining. In this other way we count $$n\binom{n-1}{k-1}$$ ways to fulfill our task.

This proves in a combinatorical way the identity which can be however verified by algebraic means.

But then our formula reduces to $$ n \sum_{k=0}^{n} (-1)^k\binom{n-1}{k-1}=n\sum_{k=1}^n(-1)^k\binom{n-1}{k-1}=0.$$

share|improve this answer
1  
The first part of your proof can even be shorter. Remember the definition of the binomial by factorials: $\small k \binom{n}{k} = k { n! \over k! (n-k)! } = {n! \over (k-1)! (n-k)! } = n { (n-1)! \over (k-1)! ((n-1)-(k-1))! } = n \binom{n-1}{k-1} $ –  Gottfried Helms Oct 25 '11 at 16:15
    
@Gottfried: I know.. However i'm in deep love with combinatorical double counting proofs so that's why i've chosen this one. However if you see i mentioned the fact that the identity may be proven algebraically. –  uforoboa Oct 25 '11 at 16:24
add comment

The identity you ask about has a direct algebraic proof using the identity you already know. Let $g(n) = \sum_{k = 0}^{n} (-1)^{k} k\binom{n}{k}$, and let $f(n) = \sum_{k = 0}^{n} (-1)^{k} \binom{n}{k}$. We will show that $g(n+1) = - f(n)$, and thus the fact that $f(n) = [n=0]$ implies $g(n) = -[n=1]$. (Here, [statement] evaluates to $1$ if statement is true and $0$ if statement is false. It's called the Iverson bracket.)

We have $$g(n+1) - g(n) = \sum_k (-1)^{k} k\left(\binom{n+1}{k} - \binom{n}{k}\right) = \sum_k (-1)^{k} k\binom{n}{k-1}$$ $$ = \sum_k (-1)^{k+1} (k+1)\binom{n}{k} = -g(n) - f(n).$$ Thus $g(n+1) = -f(n) \Longrightarrow g(n) = - f(n-1) = - [n-1=0] = -[n=1]$.


Generalization. If $g(n) = \sum_{k = 0}^{n} (-1)^{k} \binom{n}{k} b_k$, and $f(n) = \sum_{k = 0}^{n} (-1)^{k} \binom{n}{k} \Delta b_k$ (where $\Delta b_k = b_{k+1} - b_k$), then $g(n) = -f(n-1) + b_0[n=0]$. This relationship can be applied iteratively, starting with the problem above, to show that

$$\sum_{k=0}^n \binom{n}{k} (-1)^k k^{\underline{m}} = (-1)^m m![n=m],$$ and from there to $$\sum_{k=0}^n \binom{n}{k}(-1)^k k^m = \left\{ m \atop n \right\}(-1)^n n!,$$ where $\left\{ m \atop n \right\}$ is a Stirling number of the second kind.

(See, for example, Section 3 of my paper "Combinatorial Sums and Finite Differences," Discrete Mathematics, 307 (24): 3130-3146, 2007.)

share|improve this answer
add comment

Here's a purely combinatorial proof that doesn't reduce the sum to the known identity $\sum \limits_{k = 0}^{n} (-1)^{k} \binom{n}{k} = 0$.

The quantity $\binom{n}{k}k$ counts the number of ways to partition people numbered $\{1, 2, \ldots, n\}$ into a chaired committee $A$ of size $k$ and an unchaired committee $B$ of size $n-k$. Given a particular commmittee pair $(A,B)$, let $x$ be the highest-numbered person in either committee who is not the chair of $A$. Move $x$ to the other committee. This mapping is defined for all pairs of committees when $n >1$, is its own inverse (and so is one-to-one), and changes the parity on committee pairs. Thus, for $n > 1$, there are as many committee pairs with even parity as there are with odd parity. In other words, $$\sum_{k = 0}^{n} (-1)^{k} \binom{n}{k} k = 0$$ when $n > 1$.

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.