proof with induction $\sum_{k=0}^n (-1)^k \binom{n}{k} (n-k+1)^n = n!$ 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 $$
 A: 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}
