prove with induction:
$$\sum_{k=0}^n (-1)^k \binom{n}{k} (n-k+1)^n = n!$$
I'm stuck on $$n[\sum_{k=0}^{n-1} (-1)^k \binom{n-1}{k} (n-k+1)^n]= \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k+1)^n = n!$$
$$n[\sum_{k=1}^{n-1} (-1)^{k-1} \binom{n-1}{k-1} (n-k+1)^{n-1}]=\sum_{k=0}^n (-1)^k \binom{n}{k} (n-k+1)^n$$
$$\sum_{k=0}^{n} (-1)^{k-1} k \binom{n}{k} (n-k+1)^{n-1} = \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k+1)^n $$
Let's assume $$\sum_{k=0}^n (-1)^k \binom{n}{k} (n-k+1)^n = n!$$ Do the following change of variable so that it looks easier: $$k \leftarrow n-i$$ So that the equation that needs to proved is now $$\sum_{i=0}^n (-1)^{n-i} \binom{n}{n-i} (i+1)^n = n!$$ Notice that $$\binom{n}{n-i}=\binom{n}{i}$$ So why not write it as $$\sum_{i=0}^n (-1)^{n-i} \binom{n}{i} (i+1)^n = n!$$
The induction step that needs to be proved is \begin{equation} (n+1)!= \sum_{i=0}^{n+1} (-1)^{n+1-i} \binom{n+1}{i} (i+1)^{n+1} \end{equation} \begin{align} (n+1)! &= (n+1)n! \\ &= (n+1)\sum_{i=0}^n (-1)^{n-i} \binom{n}{i} (i+1)^n \\ &= (n+1)\sum_{i=0}^n (-1)^{n-i} \frac{n!}{i!(n-i)!} (i+1)^n \\ &= \sum_{i=0}^n (-1)^{n-i} \frac{(n+1)n!}{i!(n-i)!} (i+1)^n \\ &= \sum_{i=0}^n (-1)^{n-i} \frac{(n+1)!}{i!(n-i)!(n+1-i)} (n+1-i)(i+1)^n \\ &= \sum_{i=0}^n (-1)^{n-i} \frac{(n+1)!}{i!(n+1-i)!} (n+1-i)(i+1)^n \\ &= \sum_{i=0}^n (-1)^{n-i} \binom{n+1}{i} (n+1-i)(i+1)^n \\ &= \sum_{i=0}^n (-1)^{n-i} \binom{n+1}{i} (n+2-(i+1))(i+1)^n \\ &= \sum_{i=0}^n (-1)^{n-i} \binom{n+1}{i} (n+2)(i+1)^n -\sum_{i=0}^n (-1)^{n-i} \binom{n+1}{i} (i+1)(i+1)^n \\ &= (n+2)\sum_{i=0}^n (-1)^{n-i} \binom{n+1}{i} (i+1)^n +\sum_{i=0}^n (-1)^{n+1-i} \binom{n+1}{i} (i+1)^{n+1} \\ \end{align} But ( see here why ) \begin{equation} \sum_{i=0}^n (-1)^{n-i} \binom{n+1}{i} (i+1)^n = (n+2)^n \end{equation} So \begin{align} (n+1)! &= (n+2)(n+2)^n +\sum_{i=0}^n (-1)^{n+1-i} \binom{n+1}{i} (i+1)^{n+1}\\ &= (n+2)^{n+1} +\sum_{i=0}^n (-1)^{n+1-i} \binom{n+1}{i}(i+1)^{n+1}\\ &= \sum_{i=0}^{n+1} (-1)^{n+1-i} \binom{n+1}{i}(i+1)^{n+1} \end{align}