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?
 A: 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!$.
A: 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. 
A: 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.$$
A: 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.
