Finite differences of $x^n$ leading to $n!$ I'm trying to show that recursively applying finite differences to $x^n$ for $x = {1,2,3,\dots,n}$ leads to $n!$. For example, I know that the 2nd differences of $x^2$ are constant and equal $2!$ , the 3rd differences of $x^3$ lead to $3!$ and so on. So far I have generalized the pattern as $$\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^n,$$ which does indeed give $n!$ for the $n$ values that I checked. Rewriting as $$n!\sum_{k=0}^{n}(-1)^k\frac{(n-k)^n}{(n-k)!k!}$$ seems to imply that the summation is an identity equal to $1$, but why?
 A: We can also show it algebraically. We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series $A(z)$.

We obtain
\begin{align*}
\color{blue}{\sum_{k=0}^n}&\color{blue}{(-1)^k\binom{n}{k}(n-k)^n}\\
&=\sum_{k=0}^n(-1)^k\binom{n}{k}n![z^n]e^{(n-k)z}\tag{1}\\
&=n![z^n]e^{nz}\sum_{k=0}^n(-1)^k\binom{n}{k}\left(e^{-z}\right)^k\tag{2}\\
&=n![z^n]e^{nz}\left(1-e^{-z}\right)^n\tag{3}\\
&=n![z^n](1+nz+\cdots)\left(z-\frac{z^2}{2}+\cdots\right)^n\tag{4}\\
&\,\,\color{blue}{=n!}\tag{5}
\end{align*}

Comment:

*

*In (1) we use $n![z^n]e^{qz}=q^n$.


*In (2) we factor out terms independent from $k$.


*In (3) we apply the binomial theorem.


*In (4) we expand the series a little bit to better see what's going on.


*In (5) we note that only the first summand $z$ in the right-hand series of (4) contributes to $[z^n]$ when multiplied with the constant term $1$ from the left-hand series in (4).
A: Consider the backward difference operator on a monomial:
$$
\begin{align}
z^n-(z-1)^n
&=\sum_{k=1}^n(-1)^{k-1}\binom{n}{k}z^{n-k}\\
&=nz^{n-1}-\sum_{k=2}^n(-1)^k\binom{n}{k}z^{n-k}
\end{align}
$$
That is, a difference operator acting on a polynomial of degree $n$ yields a polynomial of degree $n-1$. The lead coefficient of the result is $n$ times the lead coefficient of the original polynomial. Repeating this $n$ times reduces the polynomial to degree $0$ (a constant) and multiplies the lead coefficient by $n!$.
That is,
$$
\Delta^nx^n=n!
$$
and if the original polynomial has degree less than $n$, repeating the difference $n$ times reduces it to $0$ (i.e. $\Delta^{k+1}x^k=\Delta k!=0$). Thus,
$$
\Delta^nx^k=0\qquad\text{for }k\lt n
$$
We can write the $n^\text{th}$ difference as
$$
\Delta^nf(x)=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}f(x-k)
$$
Plugging in $f(x)=x^n$ gives
$$
\Delta^nx^n=\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}(x-k)^n
$$
but we just showed that $\Delta^nx^n=n!$, therefore,
$$
\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}(x-k)^n=n!
$$
Now just plug in $x=n$.
