Proving $n! = (-1)^n \sum_{i=1}^n (-1)^i\binom{n}{i} i^n $

Question

While studying Stirling numbers of the second kind the following formula for $n!$ suddenly popped up!

$$n! = (-1)^n \sum_{i=1}^n (-1)^i\binom{n}{i} i^n $$

I was curious if I could find a "direct" proof, i.e. not involving Stirling numbers, but after trying different approaches, f.i. induction, I was stuck. So a hint would be welcome!

Answer 1

Apply the differential operator $(x \frac{d}{dx})^n$ (i.e. differentiate then multiply by $x$, a total of $n$ times) to the expression $(1-x)^n = \sum_{i=0}^n (-1)^i \binom{n}{i} x^i$. On the left hand side differentiate using the chain rule (e.g. $x\frac{d}{dx} (1-x)^n = -nx(1-x)^{n-1}$) and on the right hand side differentiate like you would a polynomial. Then take $x=1$. The answer falls right out.

Out of curiosity, did this problem come from study of the Chern-Weil homomorphism?

Answer 2

Let $ n\in\mathbb{N} $, and $ f_{n} : x\mapsto\left(\operatorname{e}^{x}-1\right)^{n} $, let's try to expand $ f_{n} $ to the $ n^{\text{th}} $ order, around $ 0 $ :

On the one hand, we have : $$ f_{n}\left(x\right)=\left(x+\underset{x\to 0}{\overset{\mathcal{O}}{}}\left(x\right)\right)^{n}=x^{n}+\underset{x\to 0}{\overset{\mathcal{O}}{}}\left(x^{n}\right) $$

On the other we have : \begin{aligned} f_{n}\left(x\right)=\sum_{k=0}^{n}{\left(-1\right)^{n-k}\binom{n}{k}\operatorname{e}^{kx}}&=\sum_{k=0}^{n}{\left(-1\right)^{n-k}\binom{n}{k}\sum_{i=0}^{n}{\frac{k^{i}}{i!}x^{i}}}+\underset{x\to 0}{\overset{\mathcal{O}}{}}\left(x^{n}\right) \\ &=\sum_{i=0}^{n}{\frac{1}{i!}\left(\sum_{k=0}^{n}{\left(-1\right)^{n-k}\binom{n}{k}k^{i}}\right)x^{i}}+\underset{x\to 0}{\overset{\mathcal{O}}{}}\left(x^{n}\right)\end{aligned}

Since, the expansion must be unique, $ \left(\forall i<n\right),\ \frac{1}{i!}\sum\limits_{k=0}^{n}{\left(-1\right)^{n-k}\binom{n}{k}k^{i}}=0$, and for $i=n $, we have : $$ \fbox{$\begin{array}{rcl}\displaystyle\sum_{k=0}^{n}{\left(-1\right)^{n-k}\binom{n}{k}k^{n}}=n!\end{array}$} $$

Another way to prove it using the same function, is to prove, first of all, by induction, that : $$ \left(\forall p\leq n\right),\ f_{n}^{\left(p\right)}\left(x\right)=\sum_{k=1}^{p}{a_{p,k}\frac{n!}{\left(n-k\right)!}\operatorname{e}^{kx}\left(\operatorname{e}^{x}-1\right)^{n-k}} $$

Where $ \left(a_{p,k}\right)_{0\leq k\leq p\leq n} $ are such that : $$ a_{p,1}=1, a_{p,p}=1, \left(\forall k\in\left[\!\left[2,p-1\right]\!\right]\right),\ a_{p+1,k}=ka_{p,k}+a_{p,k-1} $$

If we took a look at the case $ p=n $, we can see that $ f_{n}^{\left(n\right)}\left(0\right)=n! $.

If we expand $ f_{n} $ using the binomial theorem, then looked at $ f_{n}^{\left(n\right)}\left(0\right) $, we get that $ f_{n}^{\left(n\right)}\left(0\right)=\sum\limits_{k=0}^{n}{\left(-1\right)^{n-k}\binom{n}{k}k^{n}} $. Hence the equality.

Answer 3

As explained here https://math.stackexchange.com/a/550504/831983, $$ \sum_{i=0}^n (-1)^i \binom{k}{i}(k - i)^n $$ is the number of surjective functions from $\{1,2,\dotsc,n\}$ to $\{1,2,\dotsc,k\}$. If $n = k$, every surjective function is a permutation. Since there are $n!$ permutations, we obtain $$ n! = \sum_{i=0}^n (-1)^i \binom{n}{i}(n - i)^n. $$ Now reverse the order of summation, use the identity $\binom{n}{n-i} = \binom{n}{i}$ and factor out $(-1)^n$. We get \begin{align*} n! &= \sum_{i=0}^n (-1)^{n-i} \binom{n}{n-i} i^n = (-1)^n\sum_{i=0}^n (-1)^i \binom{n}{i} i^n\\ &= \underbrace{(-1)^0 \binom{n}{0} 0^n}_{= \, 0} + (-1)^n\sum_{i=1}^n (-1)^i \binom{n}{i} i^n. \end{align*}