A sum involving binomial coefficients, powers and alternating signs How to prove that
$$
\sum_{k=0}^n(-1)^{n-k}{n \choose k} k^n = n!
$$
using mathematical induction? Please, do not use definition of Stirling number etc. algebra tricks.

Actually carrying out a proof by induction seems to be quite difficult. I found it easiest to prove the following stronger result (by induction on $n$):
$$\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^m=\begin{cases}
0,&\text{if }0\le m<n\\
n!,&\text{ if }m=n\;.
\end{cases}\tag{1}$$
Assume that $(1)$ holds for a specific $n$. Then
$$\begin{align*}
(n+1)!&=(n+1)\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^n\\
&=\sum_{k=0}^n(-1)^{n-k}(n+1-k)\binom{n+1}kk^n\\
&=\sum_{k=0}^n(-1)^{n-k}(n+1)\binom{n+1}kk^n-\sum_{k=0}^n(-1)^{n-k}\binom{n+1}kk^{n+1}\\
&=\sum_{k=0}^n(-1)^{n+1-k}\binom{n+1}kk^{n+1}\\
&\qquad-\sum_{k=0}^n(-1)^{n+1-k}(n+1)\binom{n+1}kk^n\\
&=\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^{n+1}-(n+1)^{n+1}\\
&\qquad-(n+1)\sum_{k=0}^n(-1)^{n+1-k}\binom{n+1}kk^n\\
&=\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^{n+1}-(n+1)^{n+1}\\
&\qquad+(n+1)\sum_{k=0}^n(-1)^{n-k}\left(\binom{n}k+\binom{n}{k-1}\right)k^n\;.
\end{align*}$$
We’d like to show that
$$(n+1)!=\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^{n+1}\;,$$
so we’d like to show that
$$(n+1)^{n+1}-(n+1)\sum_{k=0}^n(-1)^{n-k}\binom{n+1}kk^n=0$$
or, equivalently, that
$$\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^n=(n+1)^n-\sum_{k=0}^n(-1)^{n-k}\binom{n+1}kk^n=0\;.$$
And in fact
$$\begin{align*}
\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^n&=\sum_{k=0}^{n+1}(-1)^{n+1-k}\left(\binom{n}k+\binom{n}{k-1}\right)k^n\\
&=\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n}kk^n+\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n}{k-1}k^n\\
&=-\sum_{k=0}^{n+1}(-1)^{n-k}\binom{n}kk^n+\sum_{k=0}^n(-1)^{n-k}\binom{n}k(k+1)^n\\
&=\sum_{k=0}^n(-1)^{n-k}\binom{n}k\big((k+1)^n-k^n\big)\\
&=\sum_{k=0}^n(-1)^{n-k}\binom{n}k\sum_{m=0}^{n-1}\binom{n}mk^m\\
&=\sum_{m=0}^{n-1}\binom{n}m\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^m\\
&=0\;,
\end{align*}$$
since by the induction hypothesis
$$\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^m=0$$
for $0\le m<n$. This shows that
$$\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^{n+1}=(n+1)!\;,$$
and it only remains to show that
$$\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^m=0\tag{2}$$
when $0\le m\le n$.
Now
$$\begin{align*}
\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n+1}kk^m&=\sum_{k=0}^{n+1}(-1)^{n+1-k}\left(\binom{n}k+\binom{n}{k-1}\right)k^m\\
&=\sum_{k=0}^n(-1)^{n+1-k}\binom{n}kk^m+\sum_{k=0}^{n+1}(-1)^{n+1-k}\binom{n}{k-1}k^m\\
&=-\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^m+\sum_{k=0}^n(-1)^{n-k}\binom{n}k(k+1)^m\;.
\end{align*}$$
If $m=n$, this is
$$\begin{align*}
-n!+\sum_{k=0}^n(-1)^{n-k}\binom{n}k(k+1)^n&=-n!+\sum_{k=0}^n(-1)^{n-k}\binom{n}k\sum_{\ell=0}^n\binom{n}\ell k^\ell\\
&=-n!+\sum_{\ell=0}^n\binom{n}\ell\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^\ell\\
&=-n!+\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^n+\sum_{\ell=0}^{n-1}\binom{n}\ell\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^\ell\\
&=-n!+n!+\sum_{\ell=0}^{n-1}\binom{n}\ell\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^\ell\\
&=\sum_{\ell=0}^{n-1}\binom{n}\ell\cdot0\\
&=0\;.
\end{align*}$$
And if $0\le m<n$, it’s simply
$$\begin{align*}
\sum_{k=0}^n(-1)^{n-k}\binom{n}k(k+1)^m&=\sum_{k=0}^n(-1)^{n-k}\binom{n}k\sum_{\ell=0}^m\binom{m}\ell k^m\\
&=\sum_{\ell=0}^m\binom{m}\ell\sum_{k=0}^n(-1)^{n-k}\binom{n}kk^m\\
&=\sum_{\ell=0}^m\binom{m}\ell\cdot0\\
&=0.
\end{align*}$$
This establishes $(2)$ and concludes the induction step.
