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
we have
&=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]
When $n\gt d$, $\left\{d\atop n\right\}=0$, thus, the $\color{#C00000}{\text{correction term}}$ disappears for $n\gt d$.


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
&=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}}

Mathematica code

    +(-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
$$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

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}
\left\langle d\atop p\right\rangle
This is
\left\langle d\atop p\right\rangle
\\ =
\left\langle d\atop p\right\rangle
z^{2p+2} (1-z)^{-2p-2}
\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}
\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}
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


If we take derivative of this with respect to x.


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.


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


I don’t know what to do next.

\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{\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{\ket}[1]{\left\vert #1\right\rangle}
\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{\verts}[1]{\left\vert\, #1 \,\right\vert}
$\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}}$:
\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}}
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}}}

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

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.