The k-th difference of the sequence $n^{k}$ is constant and equal to $k!$

Define the k-th difference of a sequence $\{a_n\}$ inductively as follows:

• The 1-th difference is the sequence $\{b_n\}$ given by $b_n=a_{n+1}-a_n$
• The "k+1"-th difference is the sequence $\{b_n\}$ given by $b_n=c_{n+1}-c_n$, where $\{c_n\}$ is the k-th difference of the sequence $\{a_n\}$.

Prove that, given the sequence $\{a_n\}$ such that $a_n=n^k$, for a fixed $k \in \mathbb{N}$, the k-th difference of this $\{a_n\}$ is a constant sequence and equal to $k!$

-
What did you try? –  Did Jan 22 '13 at 22:17
I had found that the differences would form a species of "binomial summation", but nothing more useful than that. Got stuck with an ugly sum. –  Aloizio Macedo Jan 22 '13 at 23:00

For a function $f: \mathbb N \to \mathbb N$, denote by $\Delta f$ its first difference, i.e. $$\Delta f(n) = f(n+1) - f(n).$$ Note that $\Delta$ is linear: $$\Delta(f+g) = \Delta f + \Delta g, \quad \Delta(af) = a\Delta(f)$$ for functions $f,g: \mathbb N \to \mathbb N$ and constants $a \in \mathbb N$.
Now let $f_k(n) = n^k$ and use induction to show $\Delta^k f_k(n) = k!$. This is clearly true for $k = 1$, so assume $k > 1$. We have $$\Delta f_k(n) = (n+1)^k - n^k = \sum_{i=0}^{k-1} \binom{k}{i} n^i = \sum_{i=0}^{k-1} \binom{k}{i} f_i (n).$$ So $$\Delta^k f_k = \Delta^{k-1} \sum_{i=0}^{k-1} \binom{k}{i} f_i = \sum_{i=0}^{k-1}\binom{k}{i}\Delta^{k-1} f_i = \binom{k}{k-1} (k-1)! = k!$$ where we used $\Delta^{k-1} f_i = 0$ for $i < k-1$.
Hint: take the 1st difference, and watch the leading monomial (use the relevant parts of the binomial expansion of $(n+1)^k$). Then use induction, while ignoring all lesser monomials.