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$.
 A: The defining equation for Stirling numbers of the second kind is
$$
\sum_{k=0}^n\left\{n\atop k\right\}\binom{x}{k}k!=x^n
$$
Thus, because
$$
\sum_{k=0}^n\binom{m}{n-2k}=2^{m-1}\left(1+\color{#C00000}{(-1)^n[m=0]}\right)
$$
we have
$$
\begin{align}
\sum_{k=0}^nk^d\binom{n}{2k}
&=2^{-d}\sum_{k=0}^n\sum_{j=0}^d\left\{d\atop j\right\}\binom{2k}{j}j!\binom{n}{2k}\\
&=2^{-d}\sum_{j=0}^d\sum_{k=0}^n\left\{d\atop j\right\}\binom{n}{j}j!\binom{n-j}{n-2k}\\
&=2^{-d}\sum_{j=0}^d\left\{d\atop j\right\}\binom{n}{j}j!\,2^{n-j-1}+\color{#C00000}{(-1)^n2^{-d-1}\left\{d\atop n\right\}n!}\\
&=2^{n-d-1}\left[\sum_{j=0}^d\left\{d\atop j\right\}\binom{n}{j}\frac{j!}{2^j}+\color{#C00000}{(-1)^n\left\{d\atop n\right\}\frac{n!}{2^n}}\right]
\end{align}
$$
When $n\gt d$, $\left\{d\atop n\right\}=0$, thus, the $\color{#C00000}{\text{correction term}}$ disappears for $n\gt d$.

Examples
For $d=1$, we get
$$
\sum_{k=0}^nk\binom{n}{2k}=2^{n-3}n+\color{#C00000}{(-1)^n\left\{1\atop n\right\}\frac{n!}{4}}
$$
For $d=2$, we get
$$
\begin{align}
\sum_{k=0}^nk^2\binom{n}{2k}
&=2^{n-3}\left(\binom{n}{1}1!\,2^{-1}+\binom{n}{2}2!\,2^{-2}\right)+(-1)^n\frac18\left\{2\atop n\right\}n!\\
&=2^{n-5}n(n+1)+\color{#C00000}{(-1)^n\left\{2\atop n\right\}\frac{n!}{8}}
\end{align}
$$

Mathematica code
f[d_]:=Evaluate[
  2^(#-d-1)Together[Expand[FunctionExpand[
    Sum[StirlingS2[d,j]Binomial[#,j]j!/2^j,{j,0,d}]]]]
    +(-1)^# StirlingS2[d,#]#!/2^(d+1)]&

Then f[3][n] yields
$$
2^{n-7}\left(n^3+3n^2\right)+\color{#C00000}{(-1)^n\left\{3\atop n\right\}\frac{n!}{16}}
$$
and f[7][n] yields
$$
2^{n-15}\left(n^7+21n^6+105n^5+35n^4-210n^3+112n^2\right)+\color{#C00000}{(-1)^n\left\{7\atop n\right\}\frac{n!}{256}}
$$
A: This is an half-answer. We have
$$(1+x)^{n}=x^{0}\binom{n}{0}+x^{1}\binom{n}{1}....+x^{n}\binom{n}{n}$$
If we take derivative of this with respect to x.
$$n(1+x)^{n-1}=1x^{0}\binom{n}{1}+2x^{1}\binom{n}{1}....+nx^{n-1}\binom{n}{n}$$
For $x=1$ we have $$n2^{n-1}=1\binom{n}{1}+2\binom{n}{2}....+n\binom{n}{n}$$
Now if we multiply the equation before this one with x and take derivative again.
$$n(1+x)^{n-1}+n(n-1)(1+x)^{n-2}=1^2x^{0}\binom{n}{1}+2^2x^{1}\binom{n}{1}....+n^2x^{n-1}\binom{n}{n}$$
For $x=1$ $$n2^{n-1}+n(n-1)2^{n-2}=1^2\binom{n}{1}+2^2\binom{n}{2}....+n^2\binom{n}{n}$$
We conclude by induction that
$$n2^{n-1}+n(n-1)2^{n-2}..+n(n-1)(n-2)...(n-d+1)2^{n-d}=1^d\binom{n}{1}+2^d\binom{n}{2}....+n^d\binom{n}{n}$$
I don't know what to do next.
A: $\newcommand{\+}{^{\dagger}}
 \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\down}{\downarrow}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\isdiv}{\,\left.\right\vert\,}
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}
 \newcommand{\wt}[1]{\widetilde{#1}}$
$\ds{\sum_{k = 0}^{n}k^{d}{n \choose 2k}:\ {\large ?}.\quad d \geq 1.\quad}$
We'll assume that $\ds{d \in {\mathbb N}}$.

$$
\half\bracks{\pars{1 + \root{x}}^{n} + \pars{1 - \root{x}}^{n}}
=\sum_{k = 0}^{n}{n \choose 2k}x^{k}
$$

$$
\sum_{k = 0}^{n}k^{d}{n \choose 2k}x^{k}
=
\pars{x\,\partiald{}{x}}^{d}\braces{\half\bracks{\pars{1 + \root{x}}^{n} + \pars{1 - \root{x}}^{n}}}
$$

$$
\sum_{k = 0}^{n}k^{d}{n \choose 2k}
=
\half\,\lim_{x \to 1}\pars{x\,\partiald{}{x}}^{d}\bracks{\pars{1 + \root{x}}^{n} + \pars{1 - \root{x}}^{n}}
$$

With $\ds{\ln\pars{x} \equiv t\quad\imp\quad x = \expo{t}}$:
\begin{align}
\sum_{k = 0}^{n}k^{d}{n \choose 2k}
&=
\half\,\lim_{t \to 0}\partiald[d]{}{t}
\bracks{\pars{1 + \expo{t/2}}^{n} + \pars{1 - \expo{t/2}}^{n}}
\\[3mm]&=
2^{n - 1}\lim_{t \to 0}\partiald[d]{}{t}\braces{\expo{nt/4}
\bracks{\cosh^{n}\pars{t \over 4} + \pars{-1}^{n}\sinh^{n}\pars{t \over 4}}}
\end{align}
A: First observe this

$$ \sum_{k=0}^{n} {n\choose 2k} = 1/2 \sum_{k=0}^{n} {n\choose k}. $$

Then here is a technique.
A: 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.
