A sum with binomial coefficients

Show that $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-2k)^{n+2}=\frac{2^{n}n(n+2)!}{6}.$$

Solution 1:

Using these three identities for $n^{\text{th}}$ differences: $$ \begin{align} \sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^n&=n!\\ \sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^{n+1}&=n!\binom{n+1}{2}\\ \sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^{n+2}&=n!\left(3\binom{n+2}{4}+\binom{n+2}{3}\right) \end{align} $$ and the fact that the $n^{\text{th}}$ difference of a polynomial of degree less than $n$ is $0$, we get $$ \begin{align} &\sum_{k=0}^n(-1)^k\binom{n}{k}(n-2k)^{n+2}\\ &=2^{n+2}\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}(k-n/2)^{n+2}\\ &=2^{n+2}\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}\left(k^{n+2}-\frac{(n+2)n}{2}k^{n+1}+\frac{(n+2)(n+1)n^2}{8}k^n+\dots\right)\\ &=2^{n+2}n!\left(\left(3\binom{n+2}{4}+\binom{n+2}{3}\right)-\frac{(n+2)n}{2}\binom{n+1}{2}+\frac{(n+2)(n+1)n^2}{8}\right)\\ &=2^nn!\binom{n+2}{3}\\[6pt] &=\frac{2^nn(n+2)!}{6} \end{align} $$

Solution 2:

The only thing I have to add on @robjohn's answer is the derivation of the identities used:

We have that

$\displaystyle\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^j=\frac{d^{j}}{d x^j}\left[(e^x-1)^n\right]\Big|_{x=0}=\frac{d^{j}}{d x^j}\left[x^n+\frac{n}{2}x^{n+1}+\frac{n(3n+1)}{24}x^{n+2}+\mathcal O(x^{n+3})\right]\Bigg|_{x=0}$,

so (for $0\leq j<n$ it is $\displaystyle\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^j=0$,)

for $j=n$ it is $\displaystyle\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^{n}=n!$,

for $j=n+1$ it is $\displaystyle\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^{n+1}=\frac{(n+1)!n}{2}$ and

for $j=n+2$ it is $\displaystyle\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^{n+2}=\frac{(n+2)!n(3n+1)}{24}$,

and that the sums on these identities are related to the Stirling numbers of the second kind (http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind), since they satisfy $\displaystyle{\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^j=n!S(j,n)}$.

One can also check out here (http://www.mathematica.gr/forum/viewtopic.php?f=59&t=36932) for a derivation using counting arguments.

Solution 3:

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

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

We thus get for the sum $$\frac{(n+2)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+3}} \sum_{k=0}^n {n\choose k} (-1)^k \exp((n-2k)z) \; dz \\ = \frac{(n+2)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+3}} \exp(nz) \sum_{k=0}^n {n\choose k} (-1)^k \exp(-2kz) \; dz \\ = \frac{(n+2)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+3}} \exp(nz) \left(1-\exp(-2z)\right)^n \; dz.$$

Categorizing the contributions to the residue according to the term from the exponential raised to the power $n$ and using the series expansion

$$1-\exp(-2z) = 2z - 2z^2 + \frac{4}{3}z^3 - \cdots$$ we get

First, with $z^n$, $$\frac{1}{2} n^2 \times 2^n.$$

Second, with $z^{n+1}$, $$n \times - {n\choose 1} 2^n.$$

Third, with $z^{n+2}$, $$1 \times {n\choose 2} 2^n + 1 \times {n\choose 1} 2^{n-1} \times \frac{4}{3}.$$

Collecting these yields $$\left(\frac{1}{2} n^2 - n^2 + \frac{1}{2} n(n-1) + \frac{2}{3} n\right) \times 2^n.$$

This is $$\left(\frac{2}{3}-\frac{1}{2}\right)n\times 2^n,$$

for a final answer of $$\frac{1}{6} n \times 2^n \times (n+2)!$$