proof of formula and calculation sum Show that following formula is true:
$$
\sum_{i=0}^{[n/2]}(-1)^i (n-2i)^n{n \choose i}=2^{n-1}n!
$$
Using formula calculate
$$
\sum_{i=0}^n(2i-n)^p{p \choose i}
$$
 A: We show by inclusion/exclusion that
$$\sum_{i=0}^n (-1)^i (c-k i)^n \binom ni = k^n n!$$
for any integer $n$ and complex $c$.  (Honestly!)  Given this, take $c=n$ and $k=2$, note that in this case the term with $i=n/2$ vanishes (if there is one), and your formula follows.
Here's the inclusion/exclusion argument.  First suppose $c>k n$ is an integer, and let $S_1,\ldots, S_n$ be disjoint $k$-tuples in $[c]=\{1,\ldots,c\}$.  We count all functions from $[n]$ to $[c]$ such that the range of $f$ intersects each $S_j$.  On the one hand, there are clearly $k^n n!$ such functions (for each $j$, there's a unique $i$ such that $f(i)\in S_j$, and there are $k$ possibilities for $f(i)$ within $S_j$).  On the other hand, the number of functions $f:[n]\to [c]$ which miss a given collection of $i$ of the $S_j$'s is $(c-k i)^n$, so we're done by inclusion/exclusion.
It's clear that the answer doesn't depend on $c$, as long as $c$ is sufficiently large.  But the left-hand side is a finite polynomial in $c$, so it must be a constant polynomial, and therefore you can pick $c$ arbitrarily.
A: By way  of commentary on the  answer by @Tad it  appears in retrospect
that the key is to realize that
$$\sum_{q=0}^{\lfloor n/2 \rfloor}
{n\choose q} (-1)^q (n-2q)^n
= \sum_{q=\lfloor n/2 \rfloor+1}^n
{n\choose q} (-1)^q (n-2q)^n$$
which is trivial once you see it (reindex $q$ by $n-q$) but escaped my
attention as I worked on the problem.
Of course the sum
$$\sum_{q=0}^n (-1)^q (c-kq)^n {n\choose q}$$
is easy to evaluate algebraically (complex variables).
Just introduce
$$(c-kq)^n = \frac{n!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp((c-kq)z) \; dz.$$
This yields for the sum
$$\frac{n!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\sum_{q=0}^n {n\choose q} (-1)^q \exp((c-kq)z) \; dz
\\ = \frac{n!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(cz)
\sum_{q=0}^n {n\choose q} (-1)^q \exp(-kqz) \; dz
\\ = \frac{n!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} \exp(cz)
\left(1-\exp(-kz)\right)^n \; dz.$$
Since $1-\exp(-kz)$ starts at $kz$ the residue is $k^n$
for a final answer of $k^n \times n!.$
The defect of  my first answer was that I did  not see the symmetry
in the sum.
