Problem in solving a question related to finite difference.

Question

Show that the $k$-th finite differences of the sequence $1^k ,2^k,3^k ,...$ are each $k!$.

I have tried but I fail when I try it proving using mathematical induction.Please help me.

Thank you in advance.

Answer 1

Use the difference of powers formula:

$$a^{k+1}-b^{k+1} = (a-b)(a^k+a^{k-1}b+\dotsb+ab^{k-1}+b^k)$$

So if $\Delta$ is the difference operator on sequences then we have

$$\Delta^{k+1}\{n^{k+1}\}_n= \Delta^k(\Delta\{n^{k+1}\}_n)=\Delta^k(\{(n+1)^{k+1}-n^{k+1}\}_n) \\=\Delta^k(\{(n+1)^k+(n+1)^{k-1}n+\dotsb+(n+1)n^{k-1}+n^k\}_n)$$

Since the difference operator is linear, we may apply it termwise.

$$\Delta^k(\{(n+1)^k\}_n)+\Delta^k(\{(n+1)^{k-1}n\}_n)+\dotsb+\Delta^k(\{(n+1)n^{k-1}\}_n)+\Delta^k(\{n^k\}_n).$$

Each term expands to a polynomial with leading term $n^k$. By the inductive hypothesis, $\Delta^k(\{n^k\}_n)=k!$, the lower order terms vanish, and there are $k+1$ terms, hence we have $(k+1)k!=(k+1)!$.

Answer 2

By the binomial theorem,

$$\Delta n^k=(n+1)^k-n^k=n^k+kn^{k-1}+\binom k2n^{k-2}+\binom k3n^{k-3}+\cdots+1-n^k\\ =kn^{k-1}+P_{k-2}(n)$$ where $P_{k-2}$ is a polynomial in $n$ of degree $k-2$.

Then if you iterate, all terms in $P_{k-2}$ will vanish and only $k!n^0$ remains.