Find $$\sum_{i\in\mathbb{N}}(n-2i)^k\binom{n}{2i+1},$$ where both $n$ and $k$ are natural numbers.

I know the following identity: $$ \sum_{i\in\{0\}\cup\mathbb{N}}i(i-1)\cdots(i-p)\binom{n}{2i+1}=(n-p-2)(n-p-3)\cdots(n-2p-2)2^{n-2p-3}. $$

But I am not sure whether this is helpful.

  • $\begingroup$ what is $k$ here? What kind of variable? $\endgroup$ – Dr. Sonnhard Graubner Jul 8 '15 at 15:37
  • $\begingroup$ $k$ is a natural number. What I am asking for is a closed form expression in terms of $n$ and $k$. $\endgroup$ – No_way Jul 8 '15 at 15:41

$\newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}}$ Using Stirling Numbers of the Second Kind, we can write monomials as sums of binomial coefficients: $$ j^k=\sum_i\stirtwo{k}{i}i!\binom{j}{i}\tag{1} $$ Thus, $$ \begin{align} \sum_{j\in\mathbb{N}}(n-2j)^k\binom{n}{2j+1} &=\sum_{j\in\mathbb{N}}(n-j)^k\binom{n}{j+1}\frac{1+(-1)^j}2\\ &=\sum_{j\in\mathbb{N}}j^k\binom{n}{n-j+1}\frac{1+(-1)^{n-j}}2\\ &=\sum_{j\in\mathbb{N}}j^k\binom{n}{j-1}\frac{1+(-1)^{n-j}}2\\ &=\frac1{n+1}\sum_{j\in\mathbb{N}}j^{k+1}\binom{n+1}{j}\frac{1+(-1)^{n-j}}2\\ &=\frac1{n+1}\sum_{i=1}^{k+1}\sum_{j\in\mathbb{N}}\stirtwo{k+1}{i}i!\binom{j}{i}\binom{n+1}{j}\frac{1+(-1)^{n-j}}2\\ &=\frac1{n+1}\sum_{i=1}^{k+1}\sum_{j\in\mathbb{N}}\stirtwo{k+1}{i}i!\binom{n+1-i}{j-i}\binom{n+1}{i}\frac{1+(-1)^{n-j}}2\\ &=\frac1{n+1}\sum_{i=1}^{k+1}\stirtwo{k+1}{i}i!\,2^{n-i}\binom{n+1}{i}-\frac12\stirtwo{k+1}{n+1}n!\\ &=\bbox[5px,border:2px solid #C0A000]{\sum_{i=1}^{k+1}\stirtwo{k+1}{i}(i-1)!\,2^{n-i}\binom{n}{i-1}\color{#C00000}{-\frac12\stirtwo{k+1}{n+1}n!}}\tag{2} \end{align} $$ Note that the part in red vanishes when $n\gt k$.

A Note on the Second to Last Equality in $\boldsymbol{(2)}$

To clarify the justification of $(2)$, notice that $$ \begin{align} \frac12\binom{n+1}{i}\sum_{j\in\mathbb{N}}\binom{n+1-i}{j-i} &=\frac12\binom{n+1}{i}(1+1)^{n+1-i}\\ &=2^{n-i}\binom{n+1}{i}\tag{3} \end{align} $$ and $$ \begin{align} \frac12\binom{n+1}{i}\sum_{j\in\mathbb{N}}(-1)^{n-j}\binom{n+1-i}{j-i} &=\frac12\overbrace{\binom{n+1}{i}}^{0\text{ if }i\gt n+1}(-1)^{n-i}\overbrace{(1-1)^{n+1-i}\vphantom{\binom{n+1}{i}}}^{0\text{ if }i\lt n+1}\\ &=-\frac12\big[i=n+1\big]\tag{4} \end{align} $$ where $[\,\cdot\,]$ are Iverson Brackets.

Therefore, $$ \sum_{j\in\mathbb{N}}\binom{n+1-i}{j-i}\binom{n+1}{i}\frac{1+(-1)^{n-j}}2 =2^{n-i}\binom{n+1}{i}-\frac12\big[i=n+1\big]\tag{5} $$

  • $\begingroup$ Thanks for the answer, but is it possible to take $i$ away from the scene? I thought the answer could be expressed in closed form in terms of $n$ and $k$ only. Maybe this is too much to ask for... $\endgroup$ – No_way Jul 8 '15 at 16:37
  • 1
    $\begingroup$ For a given $k$, this is a polynomial of degree $k$ times a power of $2$. For example, for $k=2$, $(2)$ gives $2^{n-3}(n^2+5n+4)$. $\endgroup$ – robjohn Jul 8 '15 at 16:50
  • $\begingroup$ @No_way It's unlikely that we could get rid of the polynomial factor with $k$ as well. $\endgroup$ – r9m Jul 8 '15 at 16:56
  • $\begingroup$ (+1), It was interesting reading this answer. To facilitate understanding I point out that the switch on the next to last line produces either all binomial coefficients ${n+1-i\choose q}$ yielding $2^{n+1-i}$ or those same coefficients with alternating signs which gives zero. Except when $i=n+1$ which produces zero-choose-zero so the sum does not give the correct value in that case and we must subtract it to get the correct answer. I believe we discussed this before. $\endgroup$ – Marko Riedel Jul 8 '15 at 22:13
  • $\begingroup$ @MarkoRiedel: I have added a section with more explanation for $(2)$. $\endgroup$ – robjohn Jul 8 '15 at 23:04

Suppose we seek to evaluate $$\sum_{q=0}^n (n-2q)^k {n\choose 2q+1}.$$

We observe that $$(n-2q)^k = \frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \exp((n-2q)z) \; dz.$$

This yields for the sum $$\frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \sum_{q=0}^n {n\choose 2q+1} \exp((n-2q)z) \; dz \\ = \frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp((n+1)z)}{z^{k+1}} \sum_{q=0}^n {n\choose 2q+1} \exp((-2q-1)z) \; dz$$

which is $$\frac{1}{2}\frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp((n+1)z)}{z^{k+1}} \\ \times \left(\sum_{q=0}^n {n\choose q} \exp(-qz) - \sum_{q=0}^n {n\choose q} (-1)^q \exp(-qz)\right) \; dz.$$

This yields two pieces, call them $A_1$ and $A_2.$ Piece $A_1$ is $$\frac{1}{2}\frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp((n+1)z)}{z^{k+1}} (1+\exp(-z))^n \; dz \\ = \frac{1}{2}\frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(z)}{z^{k+1}} (\exp(z)+1)^n \; dz$$ and piece $A_2$ is $$\frac{1}{2}\frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp((n+1)z)}{z^{k+1}} (1-\exp(-z))^n \; dz \\ = \frac{1}{2}\frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(z)}{z^{k+1}} (\exp(z)-1)^n \; 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)).$$

This implies that $$\sum_{n\ge q} {n\brace q} \frac{z^n}{n!} = \frac{(\exp(z)-1)^q}{q!}$$ and $$\sum_{n\ge q} {n\brace q} \frac{z^{n-1}}{(n-1)!} = \frac{(\exp(z)-1)^{q-1}}{(q-1)!} \exp(z).$$

Now to evaluate $A_1$ proceed as follows:

$$\frac{1}{2}\frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(z)}{z^{k+1}} (2+\exp(z)-1)^n \; dz \\ = \frac{1}{2}\frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(z)}{z^{k+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{1}{2}\frac{k!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(z)}{z^{k+1}} \frac{(\exp(z)-1)^q}{q!} \; dz.$$

Recognizing the differentiated Stirling number generating function this becomes $$\sum_{q=0}^n {n\choose q} 2^{n-q-1} \times q! \times {k+1\brace q+1}.$$

Now observe that when $n\gt k+1$ the Stirling number for $k+1\lt q\le n$ is zero, so we may replace $n$ by $k+1.$ Similarly, when $n\lt k+1$ the binomial coefficient for $n\lt q\le k+1$ is zero so we may again replace $n$ by $k+1.$ This gives the following result for $A_1:$

$$\sum_{q=0}^{k+1} {n\choose q} 2^{n-q-1} \times q! \times {k+1\brace q+1}.$$

Moving on to $A_2$ we observe that when $k\lt n$ the contribution is zero because the series for $\exp(z)-1$ starts at $z.$ This integral is simple and we have

$$\frac{1}{2}\frac{k!\times n!}{2\pi i} \int_{|z|=\epsilon} \frac{\exp(z)}{z^{k+1}} \frac{(\exp(z)-1)^n}{n!} \; dz.$$

Recognizing the Stirling number this yields $$\frac{1}{2} \times n! \times {k+1\brace n+1}.$$

which correctly represents the fact that we have a zero contribution when $k\lt n.$

This finally yields the closed form formula $$\sum_{q=0}^{k+1} {n\choose q} 2^{n-q-1} \times q! \times {k+1\brace q+1} - \frac{1}{2} \times n! \times {k+1\brace n+1}.$$

confirming the previous results.

This MSE link has a computation that is quite similar.


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.