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.

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?

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$.

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

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!.$$