Find $\sum_{i\in\mathbb{N}}(n-2i)^k\binom{n}{2i+1}$ 
Find $$\sum_{i\in\mathbb{N}}(n-2i)^k\binom{n}{2i+1},$$ where both $n$ and $k$ are natural numbers. 

I know the following identity:
$$
\sum_{i\in\{0\}\cup\mathbb{N}}i(i-1)\cdots(i-p)\binom{n}{2i+1}=(n-p-2)(n-p-3)\cdots(n-2p-2)2^{n-2p-3}.
$$
But I am not sure whether this is helpful.
 A: $\newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}}$
Using Stirling Numbers of the Second Kind, we can write monomials as sums of binomial coefficients:
$$
j^k=\sum_i\stirtwo{k}{i}i!\binom{j}{i}\tag{1}
$$
Thus,
$$
\begin{align}
\sum_{j\in\mathbb{N}}(n-2j)^k\binom{n}{2j+1}
&=\sum_{j\in\mathbb{N}}(n-j)^k\binom{n}{j+1}\frac{1+(-1)^j}2\\
&=\sum_{j\in\mathbb{N}}j^k\binom{n}{n-j+1}\frac{1+(-1)^{n-j}}2\\
&=\sum_{j\in\mathbb{N}}j^k\binom{n}{j-1}\frac{1+(-1)^{n-j}}2\\
&=\frac1{n+1}\sum_{j\in\mathbb{N}}j^{k+1}\binom{n+1}{j}\frac{1+(-1)^{n-j}}2\\
&=\frac1{n+1}\sum_{i=1}^{k+1}\sum_{j\in\mathbb{N}}\stirtwo{k+1}{i}i!\binom{j}{i}\binom{n+1}{j}\frac{1+(-1)^{n-j}}2\\
&=\frac1{n+1}\sum_{i=1}^{k+1}\sum_{j\in\mathbb{N}}\stirtwo{k+1}{i}i!\binom{n+1-i}{j-i}\binom{n+1}{i}\frac{1+(-1)^{n-j}}2\\
&=\frac1{n+1}\sum_{i=1}^{k+1}\stirtwo{k+1}{i}i!\,2^{n-i}\binom{n+1}{i}-\frac12\stirtwo{k+1}{n+1}n!\\
&=\bbox[5px,border:2px solid #C0A000]{\sum_{i=1}^{k+1}\stirtwo{k+1}{i}(i-1)!\,2^{n-i}\binom{n}{i-1}\color{#C00000}{-\frac12\stirtwo{k+1}{n+1}n!}}\tag{2}
\end{align}
$$
Note that the part in red vanishes when $n\gt k$.

A Note on the Second to Last Equality in $\boldsymbol{(2)}$
To clarify the justification of $(2)$, notice that
$$
\begin{align}
\frac12\binom{n+1}{i}\sum_{j\in\mathbb{N}}\binom{n+1-i}{j-i}
&=\frac12\binom{n+1}{i}(1+1)^{n+1-i}\\
&=2^{n-i}\binom{n+1}{i}\tag{3}
\end{align}
$$
and
$$
\begin{align}
\frac12\binom{n+1}{i}\sum_{j\in\mathbb{N}}(-1)^{n-j}\binom{n+1-i}{j-i}
&=\frac12\overbrace{\binom{n+1}{i}}^{0\text{ if }i\gt n+1}(-1)^{n-i}\overbrace{(1-1)^{n+1-i}\vphantom{\binom{n+1}{i}}}^{0\text{ if }i\lt n+1}\\
&=-\frac12\big[i=n+1\big]\tag{4}
\end{align}
$$
where $[\,\cdot\,]$ are Iverson Brackets.
Therefore,
$$
\sum_{j\in\mathbb{N}}\binom{n+1-i}{j-i}\binom{n+1}{i}\frac{1+(-1)^{n-j}}2
=2^{n-i}\binom{n+1}{i}-\frac12\big[i=n+1\big]\tag{5}
$$
A: Suppose we seek to evaluate
$$\sum_{q=0}^n (n-2q)^k {n\choose 2q+1}.$$
We observe that
$$(n-2q)^k = \frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{k+1}} \exp((n-2q)z) \; dz.$$
This yields 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((n-2q)z) \; dz
\\ = \frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{\exp((n+1)z)}{z^{k+1}} 
\sum_{q=0}^n {n\choose 2q+1} \exp((-2q-1)z) \; dz$$
which is
$$\frac{1}{2}\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{\exp((n+1)z)}{z^{k+1}} 
\\ \times 
\left(\sum_{q=0}^n {n\choose q} \exp(-qz)
- \sum_{q=0}^n {n\choose q} (-1)^q \exp(-qz)\right)
\; dz.$$
This yields two pieces, call them $A_1$ and $A_2.$ Piece $A_1$ is
$$\frac{1}{2}\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{\exp((n+1)z)}{z^{k+1}} 
(1+\exp(-z))^n \; dz
\\ = \frac{1}{2}\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{\exp(z)}{z^{k+1}} 
(\exp(z)+1)^n \; dz$$
and piece $A_2$ is
$$\frac{1}{2}\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{\exp((n+1)z)}{z^{k+1}} 
(1-\exp(-z))^n \; dz
\\ = \frac{1}{2}\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{\exp(z)}{z^{k+1}} 
(\exp(z)-1)^n \; dz.$$
Recall the species equation for labelled set partitions:
$$\mathfrak{P}(\mathcal{U}\mathfrak{P}_{\ge 1}(\mathcal{Z}))$$
which yields the bivariate generating function of the Stirling numbers
of the second kind
$$\exp(u(\exp(z)-1)).$$
This implies that
$$\sum_{n\ge q} {n\brace q} \frac{z^n}{n!} =
\frac{(\exp(z)-1)^q}{q!}$$
and 
$$\sum_{n\ge q} {n\brace q} \frac{z^{n-1}}{(n-1)!} =
\frac{(\exp(z)-1)^{q-1}}{(q-1)!} \exp(z).$$
Now to evaluate $A_1$ proceed as follows:
$$\frac{1}{2}\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{\exp(z)}{z^{k+1}} 
(2+\exp(z)-1)^n \; dz
\\ = \frac{1}{2}\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{\exp(z)}{z^{k+1}} 
\sum_{q=0}^n {n\choose q} 2^{n-q} (\exp(z)-1)^q \; dz 
\\ = \sum_{q=0}^n {n\choose q} 2^{n-q} \times 
q!\times \frac{1}{2}\frac{k!}{2\pi i}
\int_{|z|=\epsilon} \frac{\exp(z)}{z^{k+1}} 
\frac{(\exp(z)-1)^q}{q!} \; dz.$$
Recognizing  the differentiated  Stirling  number generating  function
this becomes
$$\sum_{q=0}^n {n\choose q} 2^{n-q-1} \times 
q! \times {k+1\brace q+1}.$$
Now observe that when $n\gt  k+1$ the Stirling number for $k+1\lt q\le
n$ is zero, so we may replace $n$ by $k+1.$ Similarly, when $n\lt k+1$
the binomial coefficient  for $n\lt q\le k+1$ is zero  so we may again
replace $n$ by $k+1.$ This gives the following result for $A_1:$
$$\sum_{q=0}^{k+1} {n\choose q} 2^{n-q-1} \times 
q! \times {k+1\brace q+1}.$$
Moving on to  $A_2$ we observe that when $k\lt  n$ the contribution is
zero because the  series for $\exp(z)-1$ starts at  $z.$ This integral
is simple and we have
$$\frac{1}{2}\frac{k!\times n!}{2\pi i}
\int_{|z|=\epsilon} \frac{\exp(z)}{z^{k+1}} 
\frac{(\exp(z)-1)^n}{n!} \; dz.$$
Recognizing the Stirling number this yields
$$\frac{1}{2} \times n! \times  {k+1\brace n+1}.$$
which correctly  represents the fact  that we have a  zero contribution
when $k\lt n.$
This finally yields the closed form formula
$$\sum_{q=0}^{k+1} {n\choose q} 2^{n-q-1} \times 
q! \times {k+1\brace q+1}
- \frac{1}{2} \times n! \times  {k+1\brace n+1}.$$
confirming the previous results.
This MSE link has a computation that is quite similar.
