Show that the $k$th forward difference of $x^n$ is divisible by $k!$ 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.
 A: 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. 
A: 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]$.
