Prove that $\sum_{x=0}^{n}(-1)^x\binom{n}{n-x} (n+1-x)^n=n!$ I figure out these thing when "playing" with numbers:
$$3^2-2.2^2+1^2=2=2!$$
$$4^3-3.3^3+3.2^3-1^3=6=3!$$
$$5^4-4.4^4+6.3^4-4.2^4+1^4=24=4!$$
So I go to the conjecture that:
$$\binom{n}{n}(n+1)^n-\binom{n}{n-1}n^n+\binom{n}{n-2}(n-1)^n-...=n!$$
or
$$\sum_{x=0}^{n}(-1)^x\binom{n}{n-x} (n+1-x)^n=n!$$
Now, how can I prove this conjecture? I've tried a lot, but still couldn't have any idea.
 A: We can test the case $n=1$:
\begin{align}\sum_{x=0}^1(−1)^x{1\choose 1−x}(1+1−x)^1&=(−1)^0{1\choose 1−0}(1+1−0)^1+ (−1)^1{1\choose 1−1}(1+1−1)^1\\
&=2+(-1)\\
&=1\\
&=1!\end{align}
Now we assume it holds for $n=k$, that is to say that $$\sum_{x=0}^k(−1)^x{k\choose k-x}(k+1−x)^k=k!$$
We need to prove that it holds for $n=k+1$, that is to say that $$\sum_{x=0}^{k+1}(−1)^x{k+1\choose k+1-x}(k+2−x)^{k+1}=(k+1)!$$
Note that $$(k+1)!=k!\times (k+1)$$
Can you continue from here?
A: Here is a variation based upon the series expansion of the exponential function
\begin{align*}
e^t=1+t+\frac{t^2}{2!}+\frac{t^3}{3!}+\cdots
\end{align*}
We use $[t^n]$ to denote the coefficient of $t^n$ in a series and write $k$ instead of $x$ for convenience only.

We obtain
  \begin{align*}
\sum_{k=0}^n(-1)^k\binom{n}{n-k}(n+1-k)^n&=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}(k+1)^n\tag{1}\\
&=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}n![t^n]e^{(k+1)t}\tag{2}\\
&=n![t^n]e^t\sum_{k=0}^n\binom{n}{k}\left(e^{t}\right)^k(-1)^{n-k}\tag{3}\\
&=n![t^n]e^t(e^t-1)^n\tag{4}\\
&=n!
\end{align*}

Comment:


*

*In (1) we change the order of summation by replacing the index $k\rightarrow n-k$.

*In (2) we consider the coefficient of $t^n$ in $e^{(k+1)t}$.

*In (3) we do a rearrangement to prepare for the binomial theorem.

*In (4) we apply the binomial theorem and note that $(e^t-1)^n$ starts with $t^n$, so that $[t^n]e^t(e^t-1)^n=1$.
A: Let's write your sum as 
$$ \bbox[lightyellow] {  
\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,k} \left( \matrix{
  n \cr 
  n - k \cr}  \right)\left( {n + 1 - k} \right)^{\,n} }  = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,n - j} \left( \matrix{
  n \cr 
  j \cr}  \right)\left( {j + 1} \right)^{\,n} }  = n!
 } \tag{1} $$
Consider the Forward Finite Difference of a function $f(x)$, and its iterations, defined as
$$ \bbox[lightyellow] {  
\eqalign{
  & \Delta _{\,x} \,f(x) = f(x + 1) - f(x)  \cr 
  & \Delta _{\,x} ^{\,2} \,f(x) = \Delta _{\,x} \,\left( {\Delta _{\,x} \,f(x)} \right) = f(x + 2) - 2f(x + 1) + f(x)  \cr 
  & \quad  \vdots   \cr 
  & \Delta _{\,x} ^{\,q} \,f(x)\quad \left| {\;0 \le {\rm integer}\,q} \right.\quad  = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n} \right)} {\left( { - 1} \right)^{\,q - k} \left( \matrix{
  q \cr 
  k \cr}  \right)f(x + k)}  \cr} 
 } \tag{2} $$
If we take $f(x)$ to be a polynomial of degree $d$
$$ \bbox[lightyellow] {  
p_{\,d} (x) = a_{\,d} \,x^{\,d}  + a_{\,d - 1} \,x^{\,d - 1}  + \; \cdots \; + a_{\,0} \,x^{\,0}  = \sum\limits_{0\, \le \,j\, \le \,d} {a_{\,j} \,x^{\,j} } 
 } \tag{3.a} $$
and we convert it into Rising Factorial (Pochammer symbol) by means of the Stirling Numbers,
$$ \bbox[lightyellow] {  
p_{\,d} (x) = b_{\,d} \,x^{\,\underline d }  + b_{\,d - 1} \,x^{\,\underline {d - 1} }  + \; \cdots \; + b_{\,0} \,x^{\,\underline 0 }  = \sum\limits_{0\, \le \,j\, \le \,d} {b_{\,j} \,x^{\,\underline {\,j\,} } } \quad \left| {\;b_{\,k}  = \sum\limits_{0\, \le \,j\, \le \,d} {a_{\,j} \,\left\{ \matrix{
  j \cr 
  k \cr}  \right\}\;} } \right.
 } \tag{3.b} $$
then, thanks to the easy expression of the finite difference for the falling factorials, it is not difficult to demonstrate that
$$ \bbox[lightyellow] {  
\eqalign{
  & \Delta ^n p_{\,d} (x) = \sum\limits_k {\left( { - 1} \right)^{n - k} \left( \matrix{
  n \cr 
  k \cr}  \right)\;p_{\,d} (x + k)}  =   \cr 
  &  = d!b_{\,d} \,\left( \matrix{
  x \cr 
  d - n \cr}  \right) + \left( {d - 1} \right)!b_{\,d - 1} \,\left( \matrix{
  x \cr 
  d - 1 - n \cr}  \right) + \; \cdots \; + 0!b_{\,0} \left( \matrix{
  x \cr 
  0 - n \cr}  \right) \cr} 
 } \tag{4} $$
which, calculated in $x=0$ gives:
$$ \bbox[lightyellow] {  
\Delta ^n p_{\,d}(0) = \sum\limits_k {\left( { - 1} \right)^{n - k} \left( \matrix{
  n \cr 
  k \cr}  \right)\;p_{\,d}(k)}  = \left\{ {\matrix{
   0 & {d < n}  \cr 
   {d!b_{\,d}  = d!a_{\,d} } & {n = d}  \cr 
   {n!b_{\,n} } & {n \le d}  \cr 
 } } \right.
 } \tag{5} $$
So your case is just a particular case , with $p_{n}(x)=(1+x)^n$, of the above which holds for all polynomials 
A: Here is a combinatorial proof: consider the set $F$ of functions $\{ 1, 2, \ldots, n \} \to \{ 1, 2, \ldots, n, n + 1 \}$, and for $k = 1, \ldots, n$, let $S_k$ be the set of such functions such that $k$ is not in the range.  Then, by inclusion-exclusion:
$$\left|F \setminus \bigcup_{k=1}^n S_k \right| = |F| - \sum_{1 \le i \le n} |S_i| + \sum_{1 \le i < j \le n} |S_i \cap S_j| - \sum_{1 \le i < j < k \le n} |S_i \cap S_j \cap S_k| + \cdots + (-1)^n |S_1 \cap \cdots \cap S_n|.$$
Now, $|F| = (n+1)^n$; for each $i$, $|S_i| = n^n$, so the second term is $-\binom{n}{1} n^n$; for each $i < j$, $|S_i \cap S_j| = (n-1)^n$, so the third term is $\binom{n}{2} (n-1)^n$; and so on.  Therefore, the sum on the right hand side is equal to the left hand side of your equation (using that $\binom{n}{n-x} = \binom{n}{x}$).  On the other hand, $F \setminus \bigcup_{k=1}^n S_k$ is exactly the set of functions such that each of $1, 2, \ldots, n$ is in the range, which is precisely the set of permutations of $\{ 1, 2, \ldots, n \}$; therefore, the left hand side is equal to $n!$.
In fact, if we let $F$ be the set of functions $\{ 1, 2, \ldots, n \} \to \{ 1, 2, \ldots, n + r \}$ instead, this argument easily generalizes to show that for $n$ a positive integer and $r$ a nonnegative integer:
$$\sum_{x=0}^n (-1)^k \binom{n}{x} (n+r-x)^n = n!.$$
A: First of all note that $$\sum_{k=0}^{n}\dbinom{n}{n-k}\left(-1\right)^{k}\left(n-k+1\right)^{n}=\sum_{k=0}^{n}\dbinom{n}{k}\left(-1\right)^{k}\left(n-k+1\right)^{n}$$ then from the special case of the Melzak's identity: $$\sum_{k=0}^{n}\left(-1\right)^{k}\dbinom{n}{k}\frac{f\left(y-k\right)}{x+k},=\frac{f\left(x+y\right)}{x\dbinom{x+n}{n}}-n!a_{n+1}\,x,y\in\mathbb{R},\,x\neq-k$$ where $f $ is an algebraic polynomial of degree $n+1$ and $a_{n+1}$ is the coefficient of the $n+1-$th power, we have, taking $f\left(z\right)=\left(z+1\right)^{n+1},\,y=n$ $$\sum_{k=0}^{n}\dbinom{n}{k}\left(-1\right)^{k}\frac{\left(n-k+1\right)^{n+1}}{-x-k}=n!-\frac{\left(n+x+1\right)^{n+1}}{x\dbinom{x+n}{n}}$$ and so $$\sum_{k=0}^{n}\dbinom{n}{k}\left(-1\right)^{k}\left(n-k+1\right)^{n}=\lim_{x\rightarrow-n-1}\left(n!-\frac{\left(n+x+1\right)^{n}}{x\dbinom{x+n}{n}}\right)={\color{red}{n!}}$$ as wanted.
A: We want to answer to this question with combinatoric method. Suppose that we have $n$ elements $(x_1,x_2,\cdots,x_n)$. We know that all permutation of these elements are $n!$ and now we want to count this $n!$ cases with the following method. 
Consider the $n+1$ elements $(x_1,x_2,\cdots,x_n,y)$ and let we want to fill $n$ places with these $n+1$ elements. All possible cases that these $n$ places can be filled with this $n+1$ elements are $(n+1)^n$ but we should remove some cases from these $(n+1)^n$ cases to just remain the permutation of $(x_1,x_2,\cdots,x_n)$.
The first case is that we choose $n-1$ element of $(x_1,x_2,\cdots,x_n)$ like $(x_1,x_2,\cdots,x_{n-1})$ and after that remove all possible cases that the $n$ places can be filled with the $(x_1,x_2,\cdots,x_{n-1},y)$ that numbers of the first case is ${n\choose {n-1}}\,n^n$.
The second case is that we choose $n-2$ elements of $(x_1,x_2,\cdots,x_n)$ like $(x_1,x_2,\cdots,x_{n-2})$ and after that remove all possible cases that the $n$ places can be filled with the $(x_1,x_2,\cdots,x_{n-2},y)$ that numbers of the second case is ${n\choose {n-2}}\,{(n-1)}^n$.
The last two cases are, we choose $1$ elements of $(x_1,x_2,\cdots,x_n)$ like $(x_1)$ and after that remove all possible cases that the $n$ places can be filled with the $(x_1,y)$ that numbers of the second case is ${n\choose {1}}\,{(2)}^n$ and the last case is $(y,y,\cdots,y)$. 
Now, if we write our discussion by Inclusion–exclusion principle then we have:
$$
\begin{array}{ll}
n!=(n+1)^n-{n\choose {n-1}}\,{(n)}^n+{n\choose {n-2}}\,{(n-1)}^n
-\cdots+(-1)^{n-1}{n\choose {1}}\,{(2)}^n+(-1)^n \\
\\
n!=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}(k+1)^n
\end{array}
$$
Example:  Let we want to count permutation of numbers $(1,2)$ then we choose a number like $5$ and consider the set $(1,2,5)$. All possible cases that $(1,2,5)$ can fill $2$ places are $9$ cases but we remove cases $(1,5)$ and $(2,5)$ and because we remove two times the case $(5,5)$, we add one to our computation. 
I hope you fine it useful.
