Question: 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}
$$

Answer: 
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.
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.