A sum with binomial coefficients Show that $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-2k)^{n+2}=\frac{2^{n}n(n+2)!}{6}.$$
 A: Using these three identities for $n^{\text{th}}$ differences:
$$
\begin{align}
\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^n&=n!\\
\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^{n+1}&=n!\binom{n+1}{2}\\
\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^{n+2}&=n!\left(3\binom{n+2}{4}+\binom{n+2}{3}\right)
\end{align}
$$
and the fact that the $n^{\text{th}}$ difference of a polynomial of degree less than $n$ is $0$, we get
$$
\begin{align}
&\sum_{k=0}^n(-1)^k\binom{n}{k}(n-2k)^{n+2}\\
&=2^{n+2}\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}(k-n/2)^{n+2}\\
&=2^{n+2}\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}\left(k^{n+2}-\frac{(n+2)n}{2}k^{n+1}+\frac{(n+2)(n+1)n^2}{8}k^n+\dots\right)\\
&=2^{n+2}n!\left(\left(3\binom{n+2}{4}+\binom{n+2}{3}\right)-\frac{(n+2)n}{2}\binom{n+1}{2}+\frac{(n+2)(n+1)n^2}{8}\right)\\
&=2^nn!\binom{n+2}{3}\\[6pt]
&=\frac{2^nn(n+2)!}{6}
\end{align}
$$
A: The only thing I have to add on @robjohn's answer is the derivation of the identities used:
We have that
$\displaystyle\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^j=\frac{d^{j}}{d x^j}\left[(e^x-1)^n\right]\Big|_{x=0}=\frac{d^{j}}{d x^j}\left[x^n+\frac{n}{2}x^{n+1}+\frac{n(3n+1)}{24}x^{n+2}+\mathcal O(x^{n+3})\right]\Bigg|_{x=0}$,
so (for $0\leq j<n$ it is $\displaystyle\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^j=0$,)
for $j=n$ it is $\displaystyle\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^{n}=n!$,
for $j=n+1$ it is $\displaystyle\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^{n+1}=\frac{(n+1)!n}{2}$ and
for $j=n+2$ it is $\displaystyle\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^{n+2}=\frac{(n+2)!n(3n+1)}{24}$,
and that the sums on these identities are related to the Stirling numbers of the second kind (http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind), since they satisfy
$\displaystyle{\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^j=n!S(j,n)}$.
One can also check out here (http://www.mathematica.gr/forum/viewtopic.php?f=59&t=36932) for a derivation using counting arguments.
A: Suppose we seek to evaluate
$$\sum_{k=0}^n {n\choose k} (-1)^k (n-2k)^{n+2}.$$
Introduce
$$(n-2k)^{n+2}
= \frac{(n+2)!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+3}} \exp((n-2k)z) \; dz.$$
We thus get for the sum
$$\frac{(n+2)!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+3}} 
\sum_{k=0}^n {n\choose k} (-1)^k \exp((n-2k)z) \; dz
\\ = \frac{(n+2)!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+3}} \exp(nz)
\sum_{k=0}^n {n\choose k} (-1)^k \exp(-2kz) \; dz
\\ = \frac{(n+2)!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+3}} \exp(nz)
\left(1-\exp(-2z)\right)^n \; dz.$$
Categorizing the  contributions to the  residue according to  the term
from  the exponential raised  to the  power $n$  and using  the series
expansion
$$1-\exp(-2z) = 2z - 2z^2 + \frac{4}{3}z^3 - \cdots$$
we get
First, with $z^n$, $$\frac{1}{2} n^2 \times 2^n.$$
Second, with $z^{n+1}$, $$n \times - {n\choose 1} 2^n.$$
Third, with $z^{n+2}$, $$1 \times {n\choose 2} 2^n
+ 1 \times {n\choose 1} 2^{n-1} \times \frac{4}{3}.$$
Collecting these yields
$$\left(\frac{1}{2} n^2 - n^2 + \frac{1}{2} n(n-1) 
+ \frac{2}{3} n\right) \times 2^n.$$
This is
$$\left(\frac{2}{3}-\frac{1}{2}\right)n\times 2^n,$$
for a final answer of
$$\frac{1}{6} n \times 2^n \times (n+2)!$$
