Prove that $n! \equiv \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k+r)^{n} $

Basically I had some fun doing this:

0
    1
1       6
    7       6
8       12
    19      6
27      18
    37      6
64      24
    61
125

etc.

starting with $k^n$ ($n=3$) and then calculating the differences. It turns out that the result after n steps is always $n!$. Pretty neat, heh? :)

Therefore:

$$ n! \equiv \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k+r)^{n} $$ where $n \in \mathbb{N}$ and $r \in \mathbb{Z}$

But how do I prove that?

Let $\mathbf E$ be the shift operator on functions on $\Bbb R$ or $\Bbb Z$: $(\mathbf{E}f)(x)=f(x+1)$. Let $\mathbf\Delta$ be the forward difference operator: $(\mathbf{\Delta} f)(x)=f(x+1)-f(x)$. Let $\mathbf 1$ be the identity operator: $\mathbf{1}f=f$. Then $\mathbf{\Delta}=\mathbf{E}-\mathbf{1}$, so $$\mathbf{\Delta}^n=(\mathbf{E}-\mathbf{1})^n=\sum_{k=0}^n(-1)^k\binom{n}k\mathbf{E}^{n-k}\;,$$ and therefore

$$\begin{align*} \mathbf{\Delta}^nf(r)&=\sum_{k=0}^n(-1)^k\binom{n}k\mathbf{E}^{n-k}f(r)\\ &=\sum_{k=0}^n(-1)^{n-k}\binom{n}kf(r+n-k)\;. \end{align*}$$

In particular, if $f(x)=x^n$, we have

$$\mathbf{\Delta}^nf(r)=\sum_{k=0}^n(-1)^{n-k}\binom{n}k(r+n-k)^n\;.\tag{1}$$

Now I claim that $\mathbf{\Delta}^nf$ is the constant function with value $n!$. This is easy to prove by induction. Suppose that it’s true for all exponents less than $n$, and note that if $f$ is a constant function, then $\mathbf{\Delta}^kf$ is identically $0$ for all $k\ge 1$. Then

$$\mathbf{\Delta}x^n=(x+1)^n-x^n=\sum_{k=0}^{n-1}\binom{n}kx^k$$ by the binomial theorem, so

$$\begin{align*} \mathbf{\Delta}^nx^n&=\sum_{k=0}^{n-1}\binom{n}k\mathbf{\Delta}^{n-1}x^k\\ &=\binom{n}{n-1}(n-1)!\\\\ &=n(n-1)!\\\\ &=n!\;, \end{align*}$$

and the induction is complete. Combining this with $(1)$ yields the desired result.

Suppose $f(x)=a_0 x^n+a_1x^{n-1}+\ldots+a_n$ be a polynomial of degree $n$. It is straightforward to check that $f(x+1)-f(x)$ is a polynomial in $x$ of degree $n-1$, with leading coefficient $n a_0$. Taking $f(x)=x^n$ and repeating this process $n$ times, we get that $$ \sum_{k=0}^n (-1)^k {n\choose k}(x+n-k)^n $$ is a polynomial in $x$ of degree 0, with leading coefficient $n!$.

Let $D = \partial/\partial x$. Then $$\begin{eqnarray*} \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(n-k+r)^{n} &=& \sum_{k=0}^{n}(-1)^{n-k} \binom{n}{k}(k+r)^{n} \\ &=& \left.\left(x D\right)^n \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} x^{k+r}\right|_{x=1} \\ &=& \left.\left(x D\right)^n x^r(x-1)^n \right|_{x=1} \\ &=& \left.D^n (x-1)^n\right|_{x=1} \\ &=& n! \end{eqnarray*}$$

Notice that in the evaluation of $\left.\left(x D\right)^n x^r(x-1)^n \right|_{x=1}$, all contributions of the form $x^m D^m x^r(x-1)^n$ with $m<n$ vanish. For more on the operator $(x D)^n$, see this question.

Since the question is tagged "combinatorics," here's a combinatorial proof. :)

Let $A_k$ be the set of all functions $f: \{1, 2, \ldots, n\} \mapsto \{1, 2, \ldots, n+r\}$ such that $f(i) = k$ for at least one $i$, where $1 \leq k \leq n$. The identity counts the number of functions in $\cap_{k=1}^n A_k$ in two different ways.

First way: The set $\cap_{k=1}^n A_k$ is the set of onto functions from $\{1, 2, \ldots, n\}$ to itself. Since an onto function from a finite set to itself must be one-to-one as well, the intersection of the $A_k$'s is the set of bijections on $\{1, 2, \ldots, n\}$. There are $n$ choices for $f(1)$, followed by $n-1$ choices for $f(2)$ given $f(1)$, and so forth. Thus: $$\text{There are $n!$ functions in } \bigcap_{k=1}^n A_k.$$

Second way: Now we want to use the principle of inclusion-exclusion. The functions in the intersection of $\bar{A}_{i_1}, \bar{A}_{i_2}, \ldots, \bar{A}_{i_k}$ are those that map from $\{1, 2, \ldots, n\}$ to $\{1, 2, \ldots, n+r\} - \{i_1, i_2, \ldots i_k\}$. There are $n-k+r$ elements in this latter set, and so there are $(n-k+r)^n$ functions in $\cap_{j=1}^k \bar{A}_{i_j}$. In addition, there are $n^n$ total functions from $\{1, 2, \ldots, n\}$ to itself. By inclusion, exclusion, then, we also have the following: $$\text{There are } \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k+r)^n \text{ functions in } \bigcap_{k=1}^n A_k.$$