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?
 A: Using Stirling numbers of the second kind we have:
$$ i^k = \sum_{j=0}^{k}{k \brace j}(i)_j = \sum_{j=0}^{k}{k \brace j}i\cdot(i-1)\cdot\ldots\cdot(i-j+1)\tag{1}$$
then, since you know that:
$$ \sum_{i=0}^{n}(i)_{p+1}\binom{n}{2i+1}=(n-p-2)_{p+1} 2^{(n-1)-2(p+1)}\tag{2}$$
you have:
$$\begin{eqnarray*} \sum_{i=0}^{n}i^k\binom{n}{2i+1}&=&\sum_{i=0}^{n}\sum_{j=0}^{k}{k \brace j}(i)_j\binom{n}{2i+1}\\&=&\sum_{j=0}^{k}{k \brace j}(n-j-1)_j\, 2^{n-(2j+1)}.\tag{3}\end{eqnarray*} $$
On the other hand, your sum is a value of a Fibonacci polynomial, by definition.
A: The first step is to find the series evaluation of 
$$S_{n}(t) = \sum_{i=0}^{n} \binom{n}{2i+1} \, t^{i}.$$
One this is done utilize the operator $\delta = t \, \frac{d}{dt} = t \, D$ to obtain the desired series. This will be of the form
$$S(1) = \left. \delta^{k} \, S_{n}(t) \right|_{t=1} = \sum_{i=0}^{n} i^{k} \, \binom{n}{2i+1}.$$ 


 $$S_{n}(t) = \frac{(1 + \sqrt{t})^{n} - (1 - \sqrt{t})^{n}}{2 \, \sqrt{t}}$$

It may be best to consider two functions in the process as well:
\begin{align}
\theta_{n}(t) &= \frac{(1 + \sqrt{t})^{n} - (1-\sqrt{t})^{n}}{\sqrt{t}} \\ 
\phi_{n}(t) &= (1+\sqrt{t})^{n} + (1 - \sqrt{t})^{n}
\end{align}
A: 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}.$$
