# 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$.

#### Solutions Collecting From Web of "Formula for $\sum_{k=0}^n k^d {n \choose 2k}$"

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

Call your sum $f_n.$ Following Wilf we introduce the generating
function
$$F(z) = \sum_{n\ge 0} f_n z^n = \sum_{n\ge 0} z^n \sum_{k=0}^n k^d {n\choose 2k} = \sum_{n\ge 0} z^n \sum_{k=0}^{\lfloor n/2\rfloor} k^d {n\choose 2k}.$$

We will extract the closed form as the coefficient $[z^n] F(z).$
Now the trick is to interchange summations, getting
$$F(z) = \sum_{k\ge 0} k^d \sum_{n\ge 2k} {n\choose 2k} z^n = \sum_{k\ge 0} k^d \sum_{n\ge 0} {n+2k\choose 2k} z^{n+2k} \\= \sum_{k\ge 0} k^d z^{2k} \sum_{n\ge 0} {n+2k\choose 2k} z^n = \sum_{k\ge 0} k^d z^{2k} \frac{1}{(1-z)^{2k+1}} \\ = \frac{1}{1-z} \sum_{k\ge 0} k^d \left(\frac{z^2}{(1-z)^2}\right)^k.$$

Now observe that
$$\sum_{q\ge 0} q^d z^q = \frac{1}{(1-z)^{d+1}} \sum_{p=0}^{d-1} \left\langle d\atop p\right\rangle z^{p+1}$$
where we have introduced Eulerian numbers.

This implies that
$$F(z) = \frac{1}{1-z} \frac{1}{(1-z^2/(1-z)^2)^{d+1}} \sum_{p=0}^{d-1} \left\langle d\atop p\right\rangle \left(\frac{z^2}{(1-z)^2}\right)^{p+1}.$$
This is
$$\frac{1}{1-z} \frac{(1-z)^{2d+2}}{(1-2z)^{d+1}} \sum_{p=0}^{d-1} \left\langle d\atop p\right\rangle \left(\frac{z^2}{(1-z)^2}\right)^{p+1} \\ = \frac{1}{1-z} \frac{(1-z)^{2d+2}}{(1-2z)^{d+1}} \sum_{p=0}^{d-1} \left\langle d\atop p\right\rangle z^{2p+2} (1-z)^{-2p-2} \\= \frac{1}{(1-2z)^{d+1}} \sum_{p=0}^{d-1} \left\langle d\atop p\right\rangle z^{2p+2} (1-z)^{2d-2p-1}.$$
Extracting coefficients from this (we need $[z^n] F(z)$) we obtain
$$\sum_{q=0}^n {n-q+d\choose d} 2^{n-q} \sum_{p=0}^{d-1} \left\langle d\atop p\right\rangle [z^q] z^{2p+2} (1-z)^{2d-2p-1}.$$
Considering the degree of the polynomial in the inner sum we see that
for a non-zero contribution we must have
$$q\ge 2p+2 \quad\text{and}\quad q\le 2d+1.$$
Therefore we restrict ourselves to $n\ge 2d+1$ and $p\le (q-2)/2$
to obtain
$$\sum_{q=2}^{2d+1} {n-q+d\choose d} 2^{n-q} \sum_{p=0}^{\lfloor (q-2)/2\rfloor} \left\langle d\atop p\right\rangle [z^q] z^{2p+2} (1-z)^{2d-2p-1} \\ = \sum_{q=2}^{2d+1} {n-q+d\choose d} 2^{n-q} \sum_{p=0}^{\lfloor (q-2)/2\rfloor} \left\langle d\atop p\right\rangle [z^{q-2p-2}] (1-z)^{2d-2p-1} \\ = 2^n \sum_{q=2}^{2d+1} {n-q+d\choose d} 2^{-q} \sum_{p=0}^{\lfloor (q-2)/2\rfloor} \left\langle d\atop p\right\rangle (-1)^{q-2p-2} {2d-2p-1\choose q-2p-2}.$$

Now the key observation at this point is that the number of terms in
the sum no longer depends on $n$ but only on $d.$

This means we can obtain a closed form by evaluating the $2d$ terms
in the sum.

We get for $d=2$ the formula
$${2}^{n} \left( 1/4\,{n\choose 2}-3/8\,{n-1\choose 2} +1/4\,{n-2\choose 2}-1/16\,{n-3\choose 2} \right)$$
which simplifies to
$$\frac{1}{32} \,{2}^{n}\;n \left( n+1 \right).$$
For $d=3$ we get
$${2}^{n} \left( 1/4\,{n+1\choose 3}-5/8\,{n\choose 3} +{\frac {7}{8}}\,{n-1\choose 3}\\-{\frac {11}{16}}\,{n-2\choose 3}+{\frac {9}{32}}\,{n-3\choose 3}-{\frac {3}{64}}\,{n-4\choose 3} \right)$$
which is
$${\frac {1}{128}}\,{2}^{n}{n}^{2} \left( n+3 \right),$$
and so on.

The last example I will present here is $d=7$ which gives
$${2}^{n} \left( 1/4\,{n+5\choose 7}-{\frac {13}{8}}\,{n+4\choose 7} +{\frac {99}{8}}\,{n+3\choose 7}-{\frac {803}{16}}\,{n+2 \choose 7}\\+{\frac {4253}{32}}\,{n+1\choose 7} -{\frac {15903}{64}}\,{n\choose 7}+{\frac {5413}{16}}\,{n-1\choose 7}-{\frac { 5441}{16}}\,{n-2\choose 7}\\+{\frac {8085}{32}}\,{n-3\choose 7} -{\frac {4389}{32}}\,{n-4\choose 7}+{\frac {13545}{256}}\,{n-5 \choose 7}-{\frac {7035}{512}}\,{n-6\choose 7} \\+{\frac {2205}{1024}}\,{n-7\choose 7}-{\frac {315}{2048}}\,{n-8\choose 7} \right)$$
which is
$${\frac {1}{32768}}\,{2}^{n}{n}^{2} \left( {n}^{5}+21\,{n}^{4} +105\,{n}^{3}+35\,{n}^{2}-210\,n+112 \right).$$
The apparent pattern in the OP that the closed form is a multiple of
$${n+d-1\choose d}$$ does not hold.

Concluding remark. Seeing the effort above it seems almost certain
that a much more elegant solution using Zeilberger / Sister Celine can
be found. In my experiments it has appeared however that the latter
method produces recurrences that have a number of terms that is not linear in $d$. The reader
may want to compare resource allocation of telescoping vs. the closed
formula above.

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.

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

First observe this

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

Then here is a technique.

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.