Find $\sum_{i\in\mathbb{N}}(n-2i)^k\binom{n}{2i+1}$

$\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} $$

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.