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?
 A: 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.
A: $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$.
A: 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$.
A: 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$.
A: 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.
A: 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}.$
