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?
Thanks in advance.
On
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$).
This is quite tough to show using induction. BUT ...
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*}