Formula for $\sum_{k=0}^n k^d {n \choose 2k}$

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

First observe this

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

Then here is a technique.

Answer 6

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.