Show that the $k$th forward difference of $x^n$ is divisible by $k!$

Question

Define the forward difference operator $$\Delta f(x) = f(x+1) - f(x)$$ I believe that if $f(x)$ is a polynomial with integer coefficients, $\Delta^k f(x)$ is divisible by k!. By linearity it suffices to consider a single monomial $f(x) = x^n$. I've checked this for small values of $n$ and $k$, and believe that a simple proof should exist, but am unable to find it.

In particular, brute force gives $$\Delta^k x^n = \sum_j x^{n-j} \left[ \binom{n}{j} \sum_i (-1)^{k-i} \binom{k}{i} i^j \right]$$ but the terms in brackets appear to have no closed form solution (see (20)-(25) of http://mathworld.wolfram.com/BinomialSums.html).

Motivation: I have an unknown integer coefficient polynomial of degree $n$ sampled at $x = 0, 1, \ldots, n$, and want to prove that all intermediate results in the classical divided difference algorithm are integers.

Answer 1

By linearity, it suffices to prove this for the polynomials $x(x - 1)\cdots(x - (n-1))$. This is just $n! {x \choose n}$. A basic property of the forward difference operator is that $\Delta {x \choose n} = {x \choose n-1}$, from which it follows that

$$\Delta^k x(x - 1)\cdots(x - (n-1)) = n! {x \choose n-k} = k! {n \choose k} x(x - 1) \cdots(x - (n-k-1))$$

and the conclusion follows.

Answer 2

This is really the same answer as that of Qiaochu Yuan, but I find the "binomial coefficients of $x$", much as I approve the notation, a bit distracting when next to ordinary binomial coefficients. One can do without them, using falling factorial powers instead: $x^\underline n=x(x-1)\ldots(x-n+1)$, which is of course the same as $n!\binom xn$. Elementarily $$ (x+1)^\underline n-x^\underline n=x^\underline{n-1}((x+1)-(x-n+1)) =nx^\underline{n-1}, $$ in other words $\Delta(x^\underline n)=nx^\underline{n-1}$ (which should remind of ordinary calculus), and $$ \Delta^k(x^\underline n)=n(n-1)\ldots(n-k+1)x^\underline{n-k} =k!\binom nkx^\underline{n-k}, $$ giving what we want. Note that I resisted the temptation to write the coefficient as $n^\underline k$ to avoid the kind of distraction I mentioned in the first sentence. Also every factor in the expression is in $\Bbb Z[x]$.