Finite differences of $x^n$ leading to $n!$

Question

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?

Answer 1

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\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).

Answer 2

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