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?

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.
