# Combinatoric proof for $\sum_{k=0}^n{n\choose k}\left(-1\right)^k\left(n-k\right)^4 = 0$ ($n\geqslant5$)

I'm trying to prove the following:

For every $n \ge 5$: $$\sum_{k=0}^n{n\choose k}\left(-1\right)^k\left(n-k\right)^4 = 0$$

I've tried cancelling one $(n-k)$, and got this: $$n\sum_{k=0}^{n-1}{n-1\choose k}\left(-1\right)^k\left(n-k\right)^3 = 0$$

I've also tried expressing the first formula as such: $$\sum_{k=0}^na_kb_k$$ Where $a_k = {n \choose k}\left(-1\right)^k$ and $b_k = \left(n-k\right)^4 = \sum_{j=0}^4{4\choose j}n^j\left(-k\right)^{4-j}$

It's easy to see that $\sum_{k=0}^n a_k = \left(1-1\right)^n = 0$ by the binomial theorem.

But I'm lost as to why this work only for n>=5. What am I missing?

• Any idea to start could be to consider the derivative of $(X-1)^n$ at $1$, evaluated in two different ways as you did for $(X-1)^n$. And to continue from there. I am not sure if this works though; it is merely an idea.
– quid
Dec 26 '14 at 12:59
• I thought of that, but not sure how this would get me to the required $\left(n-k\right)^4$...
– hyit
Dec 26 '14 at 13:01

The expression counts the number of ways to partition a set of $4$ elements into $n$ distinguishable non-empty cells, which certainly must give zero for $n \geq 5$.

The result follows by inclusion exclusion. Alternately, see Stirling numbers of the second kind for a more general view.

• Perfect! So is this the correct way of thinking? Let $A = \{a, b, c, d\}$ so that $|A| = 4$, and let $B = \{1, ..., n\}$ so that $|B| = n$. So we're looking for $|\{f: A -> B: f is injective\}|$. Total number of functions from A to B is $n^4$. Let Sk be defined as $S_k = |\{f: A -> B\\\{k\}\}|$?
– hyit
Dec 26 '14 at 13:56
• @hyit You look to be on the right track, except that you might have meant surjective. Dec 26 '14 at 14:20
• But surjective doesn't mean that the partition is distinct, does it?
– hyit
Dec 26 '14 at 14:30
• @hyit Ah, I made an error: distinguishable, not distinct. By phrasing the problem with functions on four elements, you automatically get this. What you don't automatically get is non-emptiness of partitions, which surjectivity provides. Dec 26 '14 at 14:54

$p(k)=k^4$ is a fourth degree polynomial. Let $\delta$ be the backward difference operator: $$\delta f(x) = f(x)-f(x-1).$$ Since the degree of $\delta f$ is one less than the degree of $f$, for any $n\geq 5$ we have $\delta^n p(x) = 0$.

• This is the result of the first equation in my answer. I thought that it required a bit more justification. Perhaps I was wrong :-) BTW, the operator in the question is the backward difference operator.
– robjohn
Dec 26 '14 at 19:47
• @robjohn: I always have some little problem about the nomenclature (especially because it looked natural to me to use the substitution $k\to n-k$), but the conclusion still holds by replacing the backward difference with the forward difference. Dec 26 '14 at 22:24
• I was just mentioning in case you wanted to change $\delta f(x)=f(x)-f(x-1)$ to match the question. I wasn't saying that your answer was insufficient.
– robjohn
Dec 26 '14 at 22:48
• @robjohn: I know, I know. Anyway, now it is fixed. Dec 27 '14 at 0:37

The idea of cancelling the factors of $n-k$ should work. \begin{align} \sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^m &=n\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^{m-1}\\ &-n\sum_{k=0}^n(-1)^k\binom{n-1}{k-1}(n-k)^{m-1}\\ &=n\sum_{k=0}^{n-1}(-1)^k\binom{n-1}{k}(n-k)^{m-1}\\ \end{align} For $m\le n$, induction yields \begin{align} \sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)^m &=\frac{n!}{(n-m)!}\sum_{k=0}^{n-m}(-1)^k\binom{n-m}{k}\\ &=\frac{n!}{(n-m)!}(1-1)^{n-m}\\ &=\left\{ \begin{array}{} n!&\text{if }m=n\\ 0&\text{if }m\lt n \end{array} \right. \end{align}

A Second Approach

In this answer there are three proofs of \begin{align} \sum_{j=k}^n(-1)^{j-k}\binom{n}{j}\binom{j}{k} &=\left\{\begin{array}{} 1&\text{if }n=k\\ 0&\text{otherwise} \end{array}\right.\\ &=[n=k] \end{align} where $[\dots]$ are Iverson Brackets. Furthermore, $\newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}}$ $$\sum_{k=0}^m\binom{n}{k}\,\stirtwo{m}{k}k!=n^m$$ where $\stirtwo{m}{k}$ are Stirling Numbers of the Second Kind. Therefore, \begin{align} \sum_{k=0}^n(-1)^k\binom{n}{k}(x-k)^m &=\sum_{k=0}^n\sum_{j=0}^m(-1)^{k-j}\binom{n}{k}\binom{m}{j}x^{m-j}k^j\\ &=\sum_{k=0}^n\sum_{j=0}^m\sum_{i=0}^j(-1)^{k-j}\binom{n}{k}\binom{m}{j}x^{m-j}\binom{k}{i}\stirtwo{j}{i}i!\\ &=\sum_{j=0}^m\sum_{i=0}^j(-1)^{n-j}\binom{m}{j}x^{m-j}\,[n=i]\,\stirtwo{j}{i}i!\\ &=\sum_{j=0}^m(-1)^{n-j}\binom{m}{j}x^{m-j}\stirtwo{j}{n}n! \end{align} If $m\lt n$, then either $\binom{m}{j}=0$ or $\stirtwo{j}{n}=0$. If $m=n$, the only non-zero term is $j=m$.

• Amazing! Doesn't this assume that $0^0 = 0$? Also, I know $\sum_{k=0}^n \left(-1\right)^k {n\choose k} = \left(1-1\right)^n$, but how did you get the greater formula?
– hyit
Dec 26 '14 at 13:29
• @hyit: it is just the binomial theorem; expand $(1-1)^{n-m}$
– robjohn
Dec 26 '14 at 13:31
• Then you just multiplied both parts of the equation by $\frac{n!}{\left(n-m\right)!}$ ?
– hyit
Dec 26 '14 at 13:44
• @hyit: yes; so that it matches the formula gotten by induction.
– robjohn
Dec 26 '14 at 13:52

Hint: Let $j=n-k$ be the new iterator, and use $\displaystyle{n\choose k}={n\choose n-k}$. You will arrive at a slightly simpler expression. To evaluate it, expand $(1+x)^n$, and differentiate both sides with regard to x, then multiply both sides by x. Repeat these two steps four times. Lastly, set $x=-1$.

It will be useful to know:

$$\mathbf{ Theorem.}$$ Let $$p(x)= a_0+a_1x+\cdots +a_nx^n$$ be $$\mathit{any}$$ polynomial in $$\mathbb{C}[x]$$ (of degree $$\leq n$$), then

$$\sum_{k} {n\choose k}(-1)^k p(k)=(-1)^n n! a_n.$$ So in particular when $$p$$ has degree<n, then such sums are $$0$$.

Proof: see Graham, Knuth, Patashnik, Concrete Mathematics, Addison Wesley, 1989 , formula (5.42). (As was suggested above the proof is by using difference operators. ) $$\Box$$

Concerning the original question, since $$x\mapsto (n-x)^4$$ is of degree 4 in $$x$$ but $$n\geq 5$$ we get 0.

Consider the sum

$$\sum_{k=0}^n {n\choose k} (-1)^k (n-k)^q$$

where $$q\ge 0.$$ This is

$$q! [z^q] \sum_{k=0}^n {n\choose k} (-1)^k \exp((n-k)z).$$

We obtain

$$q! [z^q] \exp(nz) \sum_{k=0}^n {n\choose k} (-1)^k \exp(-kz) \\ = q! [z^q] \exp(nz) (1-\exp(-z))^n \\ = q! [z^q] (\exp(z)-1)^n.$$

Now since $$(\exp(z)-1)^n = z^n + \cdots$$ this is zero when $$q\lt n$$ and we have the claim. Observe that the EGF here yields $$n! \times {q\brace n}.$$