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.
 A: Suggested intro: maybe these solutions don't meet the OP's specific requirements, but I think that they're worth making available anyway.

$\color{red}{n!}$ is the number of bijective functions from $A=\{1,2,\ldots,n\}$ to $A$.
Let we say that a function $f:A\to A$ has type $k$ if $|f(A)|=k$. The number of functions with type $\leq n$ is simply given by $n^n$, i.e. the number of all possible functions from $A$ to $A$. The number of functions with type $\leq(n-1)$ is given by $\binom{n}{n-1}$ (the number of ways for choosing $(n-1)$ elements in $A$) times $(n-1)^n$ (the number of functions from $A$ to a set with $(n-1)$ elements).
By the inclusion-exclusion principle, the number of functions with type $n$ (i.e. the number of bijective functions) is given by:
$$ n^n-\binom{n}{n-1}(n-1)^n+\binom{n}{n-1}(n-2)^n-\ldots = \color{red}{\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^n}. $$

Alternative proof. Let $\delta$ be the operator that maps a polynomial $p(x)$ into $p(x+1)-p(x)$.
The following properties are trivial to prove:


*

*If $\partial p$ (the degree of $p$) is $\geq 1$, the degree of $\delta p$ is $\partial p-1$;

*If the leading term of $p(x)$ is $a x^n$, the leading term of $\delta p(x)$ is $an x^{n-1}$, i.e. $\delta$ acts on the leading term like the derivative $\frac{d}{dx}$.


Since our sum is just $\delta^n p(0)$ with $p(x)=x^n$, by (2.) it follows that our sum equals $n(n-1)(n-2)\cdots 1 = n!$.
A: 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.
A: HINT
Base Case  $n=1$, check whether the equality holds (you should have just 2 terms in the sum)
Inductive Step
Assume this holds for $n = 1, 2, \ldots, N$ and show this for $n = N+1$.
You will have to simplify the terms of the summation to express 
$$
\sum_{k=0}^{N+1} (-1)^{N+1-k}{N+1 \choose k} k^{N+1}
$$
in terms of
$$
\sum_{k=0}^{N} (-1)^{N-k}{N \choose k} k^{N}
$$
