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

  • 1
    $\begingroup$ I am curious where you get this problem from? $\endgroup$ – TCL May 9 '13 at 23:49
  • 1
    $\begingroup$ This problem appears in J. Riordan's book "Combinatorial Identities", page 235. $\endgroup$ – TCL May 10 '13 at 21:43
  • $\begingroup$ I would appreciate it if the source of the problem hadn't appear before an approach was given. That is why I provided the source with an email instead of publishing it here. Thanks in advance. $\endgroup$ – akotronis May 12 '13 at 9:14
  • 1
    $\begingroup$ Since the source of the problem was mentioned anyway.., I have a solution for this one different from the one suggested by the hints on the book. I will post it if an answer doesn't appear. $\endgroup$ – akotronis May 15 '13 at 7:52

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


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.


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)!$$


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.