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

  • 2
    $\begingroup$ What did you try? $\endgroup$ – Did Jan 22 '13 at 22:17
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ You still have to justify why you can ignore the lesser ones, but that's easy. $\endgroup$ – dinoboy Jan 22 '13 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.