Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
You still have to justify why you can ignore the lesser ones, but that's easy. –  dinoboy Jan 22 '13 at 22:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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