Why is $\sum \limits_{k = 0}^{n} (-1)^{k} k\binom{n}{k} = 0$?

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.)

Answer 4

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