5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $2k$ can take values $>n$ here. $\endgroup$ – drhab Apr 24 '14 at 9:45
  • $\begingroup$ Yes. I assume ${n \choose 2k} = 0$ when $2k > n$. $\endgroup$ – user10101 Apr 24 '14 at 9:46
  • $\begingroup$ That's okay then. Maybe it's a good idea to say that in your question. You decide off course. $\endgroup$ – drhab Apr 24 '14 at 9:47
  • $\begingroup$ Check this problem. $\endgroup$ – Mhenni Benghorbal Apr 24 '14 at 18:58
  • 1
    $\begingroup$ @user10101: notice that your formulas are not correct when $1\le n\le d$. My answer has a correction term for this. $\endgroup$ – robjohn Apr 25 '14 at 0:45
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ (+1) Excellent answer. We use $$\sum_{k=0}^n {n-j\choose n-2k} = 2^{n-j-1}$$ which is fair enough. But when $n=j$ this is zero except when $n$ is even, when it is one. The value generated by the formula is $1/2$, therefore to get the right amount we add in $\frac{1}{2} 2^{-d} (-1)^n {d\brace n} n!$. The term $1/2+(1/2)^n$ toggles between zero and one. Compact formula BTW. $\endgroup$ – Marko Riedel Apr 25 '14 at 2:21
  • $\begingroup$ @MarkoRiedel: precisely. I wondered a while why the answers I got for $1\le n\le d$ were not even integers, then I realized this point. $\endgroup$ – robjohn Apr 25 '14 at 2:24
  • $\begingroup$ That should be $1/2+1/2\times (-1)^n.$ $\endgroup$ – Marko Riedel Apr 25 '14 at 2:40
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Except for the $\color{#C00000}{\text{correction term}}$, thus, for $n\gt d$, these agree with my answer. It might be nice to include a link to the Eulerian numbers. (+1) $\endgroup$ – robjohn Apr 25 '14 at 7:34
  • $\begingroup$ I just noticed your link in the above comment. I put a link into the article anyway. Your solution is without question the best that has been presented. Also, I believe it can be quite useful to present CAS code for those readers who decide to verify a post step by step. $\endgroup$ – Marko Riedel Apr 25 '14 at 21:14
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +1. This is the best way to do this. Were you inspired by Euler by any chance? ;) $\endgroup$ – Bruno Joyal Apr 25 '14 at 4:50
  • $\begingroup$ @BrunoJoyal Any way, I was frustrated with the derivative at the very end. Thanks. $\endgroup$ – Felix Marin Apr 25 '14 at 5:13
1
$\begingroup$

First observe this

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

Then here is a technique.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.