<s>[INST] Formula for $\sum_{k=0}^n k^d {n \choose 2k}$ If $d \geq 1$ is an integer, is there a general formula for $$\sum_{k=0}^n k^d {n \choose 2k}\,?$$
We know that $\sum_{k=0}^n k {n \choose 2k} = \frac{n2^n}{8}$ and $\sum_{k=0}^n k^2 {n \choose 2k} = \frac{n(n+1)2^n}{32}$.
Note that ${n \choose 2k} = 0$ when $2k > n$.
 [/INST] The answer that I presented in  my other post is more complicated than
it needs to be.

Suppose we seek to evaluate
$$\sum_{k=0}^n k^d {n\choose 2k}.$$
We observe that
$$k^d = \frac{d!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{d+1}} \exp(kz) \; dz.$$
This yields for the sum
$$\frac{d!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{d+1}} 
\sum_{k=0}^n {n\choose 2k} \exp(kz) \; dz$$
which is
$$\frac{1}{2}\frac{d!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{d+1}} 
\left(\sum_{k=0}^n {n\choose k} \exp(kz/2)
+ \sum_{k=0}^n {n\choose k} (-1)^k \exp(kz/2)\right)
\; dz.$$
This yields two pieces, call them $A_1$ and $A_2.$ Piece $A_1$ is
$$\frac{1}{2}\frac{d!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{d+1}} 
(1+\exp(z/2))^n \; dz$$
and
$$\frac{1}{2}\frac{d!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{d+1}} 
(1-\exp(z/2))^n \; dz.$$
Now to evaluate $A_1$ put $z=2w$ to get
$$\frac{d!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{(2w)^{d+1}} 
(1+\exp(w))^n \; dw
\\ = \frac{d!}{2^{d+1} \times 2\pi i}
\int_{|z|=\epsilon} \frac{1}{w^{d+1}} 
(2+\exp(w)-1)^n \; dw
\\ = \frac{d!}{2^{d+1} \times 2\pi i}
\int_{|z|=\epsilon} \frac{1}{w^{d+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{d!}{2^{d+1} \times 2\pi i}
\int_{|z|=\epsilon} \frac{1}{w^{d+1}} 
\frac{(\exp(z)-1)^q}{q!} \;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)).$$
Substitute this into the sum to get
$$\sum_{q=0}^n {n\choose q} 2^{n-q-d-1} \times q! \times
{d\brace q}
= 2^{n-d-1} \sum_{q=0}^n {n\choose q} 2^{-q} \times q! \times
{d\brace q}.$$
Now observe that  when $n\gt d$ the Stirling number  for $d\lt q\le n$
is zero,  so we may replace $n$  by $d.$ Similarly, when  $n\lt d$ the
binomial coefficient for $n\lt q\le d$ is zero so we may again replace
$n$ by $d.$ This gives the following result for $A_1:$
$$2^{n-d-1} \sum_{q=0}^d {n\choose q} 2^{-q} \times q! \times
{d\brace q}.$$
Moving on to  $A_2$ we observe that when $d\lt  n$ the contribution is
zero because the series for $1-\exp(z/2)$ starts at $z.$ We get
$$\frac{d!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{(2w)^{d+1}} 
(1-\exp(w))^n \; dw
\\ = \frac{(-1)^n d!}{2^{d+1}\times 2\pi i}
\int_{|z|=\epsilon} \frac{1}{w^{d+1}} 
(\exp(w)-1)^n \; dw
\\ = \frac{(-1)^n \times n!\times d!}{2^{d+1}\times 2\pi i}
\int_{|z|=\epsilon} \frac{1}{w^{d+1}} 
\frac{(\exp(w)-1)^n}{n!} \; dw.$$
Recognizing the Stirling number we get
$$2^{-d-1} \times (-1)^n \times n! \times {d\brace n}.$$
which correctly  represents the fact  that we have a  zero contribution
when $d\lt n.$
This finally yields the closed form formula
$$2^{n-d-1} \sum_{q=0}^d {n\choose q} 2^{-q} \times q! \times
{d\brace q}
+ 2^{-d-1} \times (-1)^n \times n! \times {d\brace n}$$
confirming the previous results.
</s>