Simplifying $\sum_{i=0}^n i^k\binom{n}{2i+1}$ What is the formula for 
\begin{eqnarray}\sum_{i=0}^n i^k\binom{n}{2i+1}?\end{eqnarray}
I tried to use the identity
$$
\sum_{i=0}^ni(i-1)\cdots(i-p)\binom{n}{2i+1}=(n-p-2)(n-p-3)\cdots(n-2p-2)2^{n-2p-3}
$$
but got into a mess. Any idea?

Suppose we seek to evaluate
$$S(n, k) = \sum_{q=0}^{n}
q^k {n\choose 2q+1}.$$
Introduce
$$q^k = 
\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{\exp(qz)}{z^{k+1}} \; dz.$$
Observe that with $k\ge 1$ we also get the correct value for $q=0.$

We obtain for the sum
$$\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+1}} 
\sum_{q=0}^{n} {n\choose 2q+1} \exp(qz)
\; dz
\\ = \frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+1}} 
\sum_{q=0}^{n} {n\choose 2q+1} \exp(2q(z/2)) \; dz
\\ = \frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+1}} \exp(-z/2)
\sum_{q=0}^{n} {n\choose 2q+1} \exp((2q+1)(z/2)) \; dz.$$
This is
$$\frac{1}{2} \frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+1}} \exp(-z/2)
((1+\exp(z/2))^n-(1-\exp(z/2))^n) \; dz.$$
Substituting $z=2w$ we obtain
$$\frac{1}{2^{k+1}} \frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{w^{k+1}} \exp(-w)
((1+\exp(w))^n-(1-\exp(w))^n) \; dw.$$
This has two pieces call them $A_1$ and $A_2.$ The piece $A_1$ is
$$\frac{1}{2^{k+1}} \frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{w^{k+1}} \exp(-w)
(1+\exp(w))^n\; dw
\\ = \frac{1}{2^{k+1}} \frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{w^{k+1}} \exp(-w)
\sum_{q=0}^n {n\choose q} 2^{n-q} (\exp(z)-1)^q
\; dw.$$
This is by convolution of generating functions
$$\frac{1}{2^{k+1}}
\sum_{q=0}^n {n\choose q} 2^{n-q} q! 
\sum_{p=0}^k {k\choose p} (-1)^{k-p} {p\brace q}.$$
The piece $A_2$ is
$$-\frac{1}{2^{k+1}} \frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{w^{k+1}} \exp(-w)
(1-\exp(w))^n \; dw
\\ = (-1)^{n+1} \frac{1}{2^{k+1}} \frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{w^{k+1}} \exp(-w)
(\exp(w)-1)^n \; dw.$$
This is
$$(-1)^{n+1} \frac{1}{2^{k+1}} n!
\sum_{p=0}^k {k\choose p} (-1)^{k-p} {p\brace n}.$$
Observe that this vanishes if $k\lt n.$
Finally note  concerning $A_1$  that if  $k\lt n$  all the  terms with
$q\gt k$ from the sum in $q$ cease to contribute owing to the Stirling
number being zero, so we may set  the upper limit to $k$ in this case.
Similarly when  $n\lt k$ the terms  with $q\gt n$ cease  to contribute
owing to the first binomial coefficient.
The end result is a polynomial in $n$ plus a correction term and we get
$$\frac{1}{2^{k+1}}
\sum_{q=0}^k {n\choose q} 2^{n-q} q! 
\sum_{p=0}^k {k\choose p} (-1)^{k-p} {p\brace q}
+ (-1)^{n+1} \frac{1}{2^{k+1}} n!
\sum_{p=0}^k {k\choose p} (-1)^{k-p} {p\brace n}.$$
