# Find $\sum_{i\in\mathbb{N}}(n-2i)^k\binom{n}{2i+1}$

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.

• what is $k$ here? What kind of variable? – Dr. Sonnhard Graubner Jul 8 '15 at 15:37
• $k$ is a natural number. What I am asking for is a closed form expression in terms of $n$ and $k$. – 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}$$

• 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... – No_way Jul 8 '15 at 16:37
• 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)$. – robjohn Jul 8 '15 at 16:50
• @No_way It's unlikely that we could get rid of the polynomial factor with $k$ as well. – r9m Jul 8 '15 at 16:56
• (+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. – Marko Riedel Jul 8 '15 at 22:13
• @MarkoRiedel: I have added a section with more explanation for $(2)$. – 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.