Calculating $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k}$$

[MountEvariste]

Find the value of $$\sum_{0 \le k \le n}(-1)^k k^n \binom{n}{k}. $$

 

[lfdahl]

Spoiler: Suggested solution

The answer is:

$\sum_{k=0}^{n}(-1)^kk^n\binom{n}{k} = (-1)^nn!\;\;\;\;(1)$

In order to show the identity, we need the following lemma:

$\sum_{k=0}^{n}(-1)^kk^m\binom{n}{k} = 0 , \, \, \, \, m = 0,1,.., n-1.\;\;\; (2)$

Proof by induction:

Consider the binomial identity: $(1-x)^n =\sum_{j=0}^{n}\binom{n}{j}(-1)^jx^j \;\;\; (3)$

Case $m = 0$: Putting $x = 1$ in $(3)$ yields: $\sum_{j=0}^{n}\binom{n}{j}(-1)^j = 0$

Case $m = 1$: Differentiating $(3)$ once yields: $-n(1-x)^{n-1} =\sum_{j=0}^{n}\binom{n}{j}(-1)^jjx^{j-1}$

Again putting $x = 1$: $\sum_{j=0}^{n}\binom{n}{j}(-1)^jj = 0$.

Assume the $m$th step is OK, where $1 \leq m < n-1$. We need to show, that our lemma also holds for step $m+1$:

Differentiate $(3)$ $m+1$ times:

$(-1)^{m+1}n(n-1)...(n-m)(1-x)^{n-m-1} = \sum_{j=0}^{n}\binom{n}{j}(-1)^jj(j-1)..(j-m)x^{j-m-1}$

Evaluating at $x = 1$:

\[\sum_{j=0}^{n}\binom{n}{j}(-1)^j\left ( j^{m+1}+c_mj^m+c_{m-1}j^{m-1} + ... + c_1j\right )=0 \\ \\ \sum_{j=0}^{n}\binom{n}{j}(-1)^jj^{m+1} + c_m\sum_{j=0}^{n}\binom{n}{j}(-1)^jj^m +c_{m-1}\sum_{j=0}^{n}\binom{n}{j}(-1)^jj^{m-1}+...+c_1\sum_{j=0}^{n}\binom{n}{j}(-1)^jj =0 \\ \therefore \sum_{j=0}^{n}\binom{n}{j}(-1)^jj^{m+1} = 0.\]

Now we are well prepared to prove, that $(1)$ holds. This will be another proof by induction:

Let $S_n = \sum_{k=0}^{n}(-1)^kk^n\binom{n}{k}$. Then we have:

$S_0 = 1 = (-1)^00!$, and $S_1 = (-1)^00^1\binom{1}{0}+(-1)^11^1\binom{1}{1} = -1 = (-1)^11!$

Therefore, we may assume, that $(1)$ holds for some step $ n > 1$: $S_n = (-1)^nn!$

\[S_{n+1} = \sum_{k=0}^{n+1}(-1)^kk^{n+1}\binom{n+1}{k} = \sum_{k=1}^{n+1}(-1)^kk^n\frac{(n+1)!}{(k-1)!(n+1-k)!}\\= \sum_{j=0}^{n}(-1)^{j+1}(j+1)^n\frac{(n+1)n!}{j!(n-j)!}= -(n+1)\sum_{j=0}^{n}(-1)^j(j+1)^n\binom{n}{j} \\= -(n+1)\sum_{j=0}^{n}(-1)^j\left ( 1+\binom{n}{1}j+\binom{n}{2}j^{2}+...+\binom{n}{n-1}j^{n-1}+j^n \right )\binom{n}{j} \\=-(n+1)\left ( \sum_{m=0}^{n-1}\binom{n}{m}\sum_{j=0}^{n}(-1)^jj^{m}\binom{n}{j}+S_n\right )\]

With the help of our lemma, the double sum in the parenthesis equals 0, so we are left with:

\[S_{n+1} = -(n+1)S_n = (-1)^{n+1}(n+1)! \;\;\; q.e.d.\]