$$\sum_{i=0}^n (-1)^i {n\choose n-i}(n-i)^m=0$$ for $m<n$
I know one solution for this question is counting the onto functions can be made from set$ A $with $m$ elements to the set $B$ with $n$ elements,we know that if $m<n$then there is no such a function and the equality is proven using inclusion-exclusion principal,but I'm looking for a algebraic solution for this equality. I've tried many kinds of inductive reasoning,but all failed,so I wont rewrite them. any hint would be appreciated.
Note first that
$$\sum_{i=0}^n(-1)^i\binom{n}{n-i}(n-i)^m=(-1)^n\sum_{i=0}^n(-1)^i\binom{n}ii^m\;,$$
so we might as well try to prove that
$$\sum_{i=0}^n(-1)^i\binom{n}ii^m=0$$
whenever $m<n$.
Suppose not, let $m$ be the smallest exponent for which there is a counterexample, and let $n$ be minimal among counterexamples for $m$. In other words, we’re assuming that $m<n$ and
$$\sum_{i=0}^n(-1)^i\binom{n}ii^m\ne 0\;,\tag{1}$$
but
$$\sum_{i=0}^r(-1)^i\binom{r}ii^s=0\quad\text{whenever}\quad m<s<r\;,\tag{2}$$
and
$$\sum_{i=0}^r(-1)^i\binom{r}ii^m=0\quad\text{whenever}\quad m<r<n\;.\tag{3}$$
(In terms of the approach to induction usually taught to undergraduates, $(2)$ and $(3)$ are the induction hypothesis.)
Assume for now that $m<n-1$. Then
$$\begin{align*} \sum_{i=0}^n(-1)^i\binom{n}ii^m&=\sum_{i=0}^n(-1)^i\left(\binom{n-1}i+\binom{n-1}{i-1}\right)i^m\\ &=\sum_{i=0}^n(-1)^i\binom{n-1}ii^m+\sum_{i=0}^n(-1)^i\binom{n-1}{i-1}i^m\\ &=\sum_{i=0}^{n-1}(-1)^i\binom{n-1}ii^m+\sum_{i=0}^{n-1}(-1)^{i+1}\binom{n-1}i(i+1)^m\tag{4}\\ &\overset{(1)}=0+\sum_{i=0}^{n-1}(-1)^{i+1}\binom{n-1}i(i+1)^m\\ &\overset{(2)}=\sum_{i=0}^{n-1}(-1)^{i+1}\binom{n-1}i\sum_{k=0}^m\binom{m}ki^k\\ &=\sum_{k=0}^m\binom{m}k\sum_{i=0}^{n-1}(-1)^{i+1}\binom{n-1}ii^k\\ &=0\;. \end{align*}$$
The step labelled $(1)$ uses the second part of the induction hypothesis (i.e., line $(3)$), the step labelled $(2)$ uses the binomial theorem, and the last step uses the first part of the induction hypothesis (i.e., line $(2)$).
If $m=n-1$, we pick up at $(4)$:
$$\begin{align*} \sum_{i=0}^n(-1)^i\binom{n}ii^{n-1}&=\sum_{i=0}^{n-1}(-1)^i\binom{n-1}ii^{n-1}+\sum_{i=0}^{n-1}(-1)^{i+1}\binom{n-1}i(i+1)^{n-1}\\ &=\sum_{i=0}^{n-1}(-1)^i\binom{n-1}ii^{n-1}+\sum_{i=0}^{n-1}(-1)^{i+1}\binom{n-1}i\sum_{k=0}^{n-1}\binom{n-1}ki^k\\ &=\sum_{i=0}^{n-1}(-1)^i\binom{n-1}ii^{n-1}+\sum_{k=0}^{n-1}\binom{n-1}k\sum_{i=0}^{n-1}(-1)^{i+1}\binom{n-1}ii^k\\ &\overset{(1)}=\sum_{i=0}^{n-1}(-1)^i\binom{n-1}ii^{n-1}+\sum_{i=0}^{n-1}(-1)^{i+1}\binom{n-1}ii^{n-1}\\ &=\sum_{i=0}^{n-1}(-1)^i\binom{n-1}ii^{n-1}-\sum_{i=0}^{n-1}(-1)^i\binom{n-1}ii^{n-1}\\ &=0\;. \end{align*}$$
The step labelled $(1)$ uses the induction hypothesis, which ensures that
$$\sum_{i=0}^{n-1}(-1)^{i+1}\binom{n-1}ii^k=0$$
for $k<n-1$.
Thus, there is no counterexample, and the result is established.