Simplifying the combinatorial expression $\sum_{k=0}^n (-1)^k {n \choose k} (x - k)^m$ Can someone help me make sense of the following expression:
$$f(x) = \sum_{k=0}^n (-1)^k {n \choose k} (x - k)^m$$
Where $m$ is an integer.
I ran into a special case of it while solving a recurrence relation.
I observe the following behavior:
When $m < n$, this is identically zero.
When $m \geq n$, it is a polynomial of degree $m - n$. 
But I can't seem to make sense of why this is. I tried using the binomial theorem on $(x-k)^m$ to say
$$f(x) = \sum_{k=0}^n \sum_{j=0}^m (-1)^{k + j} {n \choose k} {m \choose j} x^{m-j} k^j$$
but this seems to just make it messier.
 A: This sum appears frequently at this site. One approach is to put
$$(x-k)^m = \frac{m!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+1}} \exp((x-k)z) \; dz$$
in order to obtain an alternate closed form.
This yields for the sum
$$\frac{m!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+1}} \exp(xz)
\sum_{k=0}^n (-1)^k {n\choose k} \exp(-kz)\;dz$$
which is
$$\frac{m!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+1}} \exp(xz)
\left(1-\exp(-z)\right)^n \; dz
\\ = \frac{m!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+1}} \exp((x-n)z)
\left(\exp(z)-1\right)^n \; dz
\\ = \frac{n! \times m!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+1}} \exp((x-n)z)
\frac{\left(\exp(z)-1\right)^n}{n!} \; dz$$
Extracting coefficients we obtain
$$n!\times m! \times
\sum_{q=0}^m \frac{(x-n)^{m-q}}{(m-q)!} 
\frac{1}{q!} {q\brace n}
\\ = n! \times
\sum_{q=0}^m {m\choose q} {q\brace n} (x-n)^{m-q}.$$
This  alternate   expression  reveals  what  is   happening  here.  In
particular the Stirling number ensures that the sum is zero when $m\lt
n.$  Moreover since $q$  only starts  contributing at  $q=n$ we  get a
polynomial of degree $m-n.$ This was to be shown.
Remark. Here we have used the fact that the combinatorial species of set partitions with sets marked is
$$\mathfrak{P}(\mathcal{U}(\mathfrak{P}_{\ge 1}(\mathcal{Z})))$$
which gives the generating function
$$G(z, u) = \exp(u(\exp(z)-1))$$
so that
$${q\brace n} = q! [z^q] \frac{(\exp(z)-1)^n}{n!}.$$
A: Consider the action of the backward difference operator $\delta$ that maps a polynomial $p(x)$ to $p(x)-p(x-1)$. You are just computing $\delta^n$ applied to $x^m$: notice that every time we apply $\delta$, the degree of the resulting polynomial decreases by one.
