Prove $\sum_{k = 0}^{n}(-1)^{n - k} \binom{n}{k} \cdot k^n = n!$ and $\sum_{k = 0}^{n}(-1)^{n - k} \binom{n}{k} \cdot k^m = 0$

Question

Prove $$\sum_{k = 0}^{n}(-1)^{n - k} \binom{n}{k} \cdot k^n = n! \qquad\text{and}\qquad \sum_{k = 0}^{n}(-1)^{n - k} \binom{n}{k} \cdot k^m = 0,$$ where $m \in \{0, 1, 2, \cdots, n - 1\}$.

To be honest, I tried to use some combinatorial ideas but was not able to see interconnections. Also, I had an idea to prove it using induction but failed to do that either.

Help will be much appreciated! I just got stuck and don't see any continuation of solution for this problem

Answer 1

Here are some hints:

1. The $(-1)^{n - k}$ suggests to interpret this as inclusion exclusion.
2. $k^n$ is the number of functions from an $n$ element set to a $k$ element set
3. $n!$ is the number of functions from an $n$ element set to an $n$ element set which are injections/surjections/bijections

So you can think of the term $\binom{n}{k}k^n$ as the number of functions from $\{1,\dots,n\} \to \{1,\dots,n\}$ whose image is contained in a chosen $k$-element subset of the codomain.

Answer 2

Consider the exponential generating function

$$ f(x) = \sum_{m=0}^{\infty} \frac{A_m}{m!} x^m, \qquad A_m := \sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k} k^m. $$

Then it follows that

\begin{align*} f(x) &= \sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k} \sum_{m=0}^{\infty} \frac{(kx)^m}{m!} \\ &= \sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k} e^{kx} \\ &= (e^x - 1)^n. \end{align*}

Writing $e^x - 1 = x g(x)$ for $g(x) = \sum_{j=0}^{\infty} \frac{x^j}{(j+1)!}$,

$$ f(x) = x^n g(x)^n . $$

In particular, the Maclaurin series for $f$ about $x = 0$ begins with $ f(x) = x^n + \cdots $, which translates to the desired fact:

$$ A_m = \begin{cases} 0, &\text{if $m < n$}, \\ n!, &\text{if $m = n$}. \end{cases} $$

In general, this computation shows that

$$ A_m = \sum_{\substack{j_1\geq1,\dots,j_n\geq1 \\ j_1+\cdots+j_n=m}} \binom{m}{j_1,\dots,j_n} \tag{1} $$

for all $m = 0, 1, 2, \dots $.

---

Alternatively, here is an extended version of @Trevor Gunn's answer: Let $[n] = \{1, \dots, n\}$. Then define

$$ X_i = \{ f \in [n]^{[m]} : i \notin \operatorname{range}(f) \} = ([n]\setminus\{i\})^{[m]} $$

for each $i = 1, 2, \dots, n$ and

$$ X_{\varnothing} = [n]^{[m]}, \qquad X_I = \bigcap_{i\in I} X_i, $$

for each non-empty $I \subseteq [n]$. Then $A_m$ can be written as

$$ A_m = \sum_{k=0}^{n} (-1)^k \binom{n}{k} (n-k)^m = \sum_{I\subseteq[n]} (-1)^{\left| I \right|} \left| X_I \right|. $$

Now by the inclusion-exclusion principle, it follows that

\begin{align*} A_m &= \left| \{ f \in [n]^{[m]} : f \notin X_1 \cup \cdots \cup X_n \} \right| \\ &= \text{[# of surjections from $[m]$ to $[n]$]}. \tag{2} \end{align*}

Note that this formula also matches the formula $\text{(1)}$ in the first solution. Now the desired answer easily follows from $\text{(2)}$.

Answer 3

This problem has appeared a number of times. Using coefficient extractors we have

$$\sum_{k=0}^n (-1)^{n-k} {n\choose k} k^m \\ = m! [z^m] \sum_{k=0}^n (-1)^{n-k} {n\choose k} \exp(kz) \\ = m! [z^m] (\exp(z)-1)^n.$$

Now $\exp(z)-1 = z+\cdots$ so $(\exp(z)-1)^n = z^n + \cdots$ and therefore the coefficient extractor returns zero when $m\lt n$ and one when $m=n$, which is the claim.

Answer 4

Note that the Finite difference (forward, with unit step) of a function is defined as $$ \Delta \,f(x) = f(x + 1) - f(x) $$ its iteration being $$ \Delta ^{\,n} f(x) = \Delta \left( {\Delta ^{\,n - 1} f(x)} \right) = \sum\limits_{0\, \le \,k\, \le \,n} {\left( { - 1} \right)^{\,n - k} \left( \matrix{ n \cr k \cr} \right)f(x + k)} $$

Now, since any polynomial can be expressed as a Newton series that implies that the $n$-th difference of a polynomial of degree $n$ is constant and equal to $n!$ times the leading coefficient, i.e. $$ \Delta ^{\,n} \left( {a_{\,n} x^{\,n} + a_{\,n - 1} x^{\,n - 1} + \cdots + a_{\,0} } \right) = n! a_{\,n} $$ as well as that the $n$-th difference of a polynomial of degree $m < n$ is null.

Therefore $$ \eqalign{ & \sum\limits_{0\, \le \,k\, \le \,n} {\left( { - 1} \right)^{\,n - k} \left( \matrix{ n \cr k \cr} \right)\left( {x + k} \right)^{\,n} } = \Delta ^{\,n} (x^{\,n} ) = n!\quad \left| {\;\forall x \in C} \right. \cr & \sum\limits_{0\, \le \,k\, \le \,n} {\left( { - 1} \right)^{\,n - k} \left( \matrix{ n \cr k \cr} \right)\left( {x + k} \right)^{\,m} } = \Delta ^{\,n} (x^{\,m} ) = 0\quad \left| {\;m < n,\;\forall x \in C} \right. \cr} $$