<s>[INST] 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.
 [/INST] 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?
</s>