# How to complete this proof involving factorials

Recently I came across the following identity, but if I try proving it with induction, then I get stuck.

$$n! = \sum^n_{k=0}(-1)^{n-k}\binom{n}{k}(k+1)^n$$

While trying my induction step I get the following:

$$(n+1)! = (n+1)\sum^n_{k=0}(-1)^{n-k}\binom{n}{k}(k+1)^n$$ $$(n+1)! = \sum^n_{k=0}(-1)^{n-k}\binom{n+1}{k+1}(k+1)^{n+1}$$ $$\vdots$$ $$(n+1)! = \sum^{n+1}_{k=0}(-1)^{n+1-k}\binom{n+1}{k}(k+1)^{n+1}$$

(Question) How do I complete the proof?

Using the $$[x^k]:f(x)$$ to represent the coeficient of $$x^k$$ in the power series for $$f(x)$$.
Note that $$\begin{eqnarray*} \frac{(k+1)^n}{n!} =[x^n]: e^{(k+1)x}. \end{eqnarray*}$$ Now divide your equation by $$n!$$ and we have $$\begin{eqnarray*} \sum_{k-0}^{n} (-1)^{n-k} \binom{n}{k}\frac{(k+1)^n}{n!} &=&[x^n]: \sum_{k-0}^{n} (-1)^{n-k} \binom{n}{k} e^{(k+1)x} \\&=& [x^n]:e^x(e^x-1)^n =\color{red}{1}. \end{eqnarray*}$$
Alternatively, and proceeding from a more general result, we have that the Finite Difference of first order, and the next iterated ones, are defined as \eqalign{ & \Delta _{\,x} f(x) = f(x + 1) - f(x) \cr & \Delta _{\,x} ^n f(x) = \Delta _{\,x} \left( {\Delta _{\,x} ^{n - 1} f(x)} \right) = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{n - k} \binom{n}{k}f(x + k)} \cr}
Then, if $$f(x)$$ is a polynomial of degree $$n$$ \eqalign{ & f(x) = p_{\,n} (x) = a_{\,n} x^{\,n} + a_{\,n - 1} x^{\,n - 1} + \cdots + a_{\,0} = \cr & = n!a_{\,n} \binom{x}{n} + \left( {n - 1} \right)!b_{\,n - 1} \binom{x}{n-1} + \cdots + b_{\,0} \binom{x}{0} \cr} the $$n$$th order Difference will leave only the leading coefficient in the Newton expression, i.e. $$\Delta _{\,x} ^n p_{\,n} (x) = n!a_{\,n} \binom{x}{n-n} = n!a_{\,n}$$
This for whichever $$p_n(x)$$ and in particular for $$x^n$$ (then computed at $$x=1$$).