Vtyjkyuk

prove with induction:

$$sum_k=0^n (-1)^k binomnk (n-k+1)^n = n!$$

I'm stuck on
$$n[sum_k=0^n-1 (-1)^k binomn-1k (n-k+1)^n]= sum_k=0^n (-1)^k binomnk (n-k+1)^n = n!$$

$$n[sum_k=1^n-1 (-1)^k-1 binomn-1k-1 (n-k+1)^n-1]=sum_k=0^n (-1)^k binomnk (n-k+1)^n$$

$$sum_k=0^n (-1)^k-1 k binomnk (n-k+1)^n-1 = sum_k=0^n (-1)^k binomnk (n-k+1)^n $$

Let's assume
$$sum_k=0^n (-1)^k binomnk (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 binomnn-i (i+1)^n = n!$$
Notice that
$$binomnn-i=binomni$$
So why not write it as
$$sum_i=0^n (-1)^n-i binomni (i+1)^n = n!$$

The induction step that needs to be proved is
beginequation
(n+1)!=
sum_i=0^n+1 (-1)^n+1-i binomn+1i (i+1)^n+1
endequation
beginalign
(n+1)! &= (n+1)n! \
&= (n+1)sum_i=0^n (-1)^n-i binomni (i+1)^n \
&= (n+1)sum_i=0^n (-1)^n-i fracn!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 binomn+1i (n+1-i)(i+1)^n \
&= sum_i=0^n (-1)^n-i binomn+1i (n+2-(i+1))(i+1)^n \
&= sum_i=0^n (-1)^n-i binomn+1i (n+2)(i+1)^n
-sum_i=0^n (-1)^n-i binomn+1i (i+1)(i+1)^n \
&= (n+2)sum_i=0^n (-1)^n-i binomn+1i (i+1)^n
+sum_i=0^n (-1)^n+1-i binomn+1i (i+1)^n+1 \
endalign
But ( see here why )
beginequation
sum_i=0^n (-1)^n-i binomn+1i (i+1)^n
=
(n+2)^n
endequation
So
beginalign
(n+1)! &= (n+2)(n+2)^n +sum_i=0^n (-1)^n+1-i binomn+1i (i+1)^n+1\
&= (n+2)^n+1 +sum_i=0^n (-1)^n+1-i binomn+1i(i+1)^n+1\
&= sum_i=0^n+1 (-1)^n+1-i binomn+1i(i+1)^n+1
endalign