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.

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!$.
