Another identity with binomial coefficients

Question

I'm looking for an easy way to prove this identity

$$\sum_{j=0}^{n}{(-1)^j j (n-j) {n \choose j}} = 0$$ for $n > 2$.

I know this can be proven by differentiating $(1+x)^n = \sum x^j{n \choose j}$ twice, taking a linear combination and substituting $x=-1$, but I want something different, hopefully more elegant.

Answer 1

To avoid differentiation, you may observe that $$ (n-j)j{n\choose j} = n(n-1) {n-2\choose j-1},\quad n>2,\,j\geq1,\tag 1 $$ then, by the binomial theorem you just have, for $n >2$, $$ \begin{align} \sum_{j=0}^n(-1)^j(n-j)j{n\choose j} &=\sum_{j=1}^{n-1}(-1)^j(n-j)j{n\choose j}\\\\&=-n(n-1)\sum_{j=1}^{n-1}(-1)^{j-1}{n-2\choose{j-1}}\\\\ &=-n(n-1)\sum_{j=0}^{n-2}(-1)^j{n-2\choose{j}}\\\\ &=-n(n-1)(1-1)^{n-2} \\\\ & =0.\tag 2 \end{align} $$

Answer 2

This result for odd $n$ follows from symmetry. Binomial coefficients are symmetric: ${n \choose j} = {n \choose n - j}$. Also, let $f(j) = j(n - j)$. Then $f(n - j) = f(j)$. Finally, let's let the term in your sum be $g(j) = (-1)^j j (n-j) {n \choose j}$. Then if $n$ is odd $g(j) = - g(n - j)$. So pairing up the terms, everything cancels out to $0$. For the case of even $n$, we should be able to use the fact that ${n + 1\choose j} = {n \choose j} + {n \choose j - 1}$, and reduce to the odd case.

Answer 3

A combinatorial interpretation of the unsigned terms in the sum is: choose a set of $j$ elements, and then distinguish one element in the set and one element not in the set.

To prove the identity, it suffices to find a matching between the results of doing this (henceforth configurations) when $j$ is even and doing this when $j$ is odd. [That is, we are doing D.I.E. where there are no exceptions.]

(Intuition: we want to move one element from either inside the set out or outside the set in; that will change the parity of the set. Naïvely we might choose to make this a distinguished element, but then the resulting configuration has two elements distinguished either in the set or out of it. We might try again with always moving 1. This almost works, but if 1 is distinguished we run into the same problem.)

To go from an even-$j$ configuration to an odd-$j$ one, take smallest-numbered element which is not distinguished, and either add it to or remove it from the set. The result is another configuration, with $j$ (the set size) having the opposite parity. Moreover, since the same elements are distinguished, performing the same procedure will either remove it from or add it back to the set, and so it is its own inverse operation; hence a bijection.

Note: this proof also suggests why $n>2$ is required: If $n = 2$, then the only term that contributes to that sum is $j=1$, and in this case, the configuration has no non-distinguished elements to rearrange.

---

As a bonus, this argument immediately produces the more general result that

$$\sum_j (-1)^j \binom{j}{a}\binom{n-j}{a}\binom{n}{j} = 0$$

where $a$ is fixed number and $n>2a$. Proof: distinguish $a$ elements inside and outside the set.

This is not a combinatorialization of Colm's proof, which is what I was originally trying for. For that, the involution such that it trades the set for its complement when $n$ is even. Perhaps you can generalize in a different direction by thinking of things that way.