$\Delta^ny = n!$ , difference operator question.

Question

I was looking in a numerical analysis book and found the statement: if $y=x^n$ and the difference is $h=1$ then $\Delta^ny = n!$ and $\Delta^{n+1}y = 0$.

Here $\Delta y = y(x+1)-y(x)=(x+1)^n -x^n$, ($\Delta$ is the difference operator). $\Delta^{2} y = \Delta\Delta y = \Delta(y(x+1)-y(x)) = \Delta y(x+1)-\Delta y(x) = $ $((x+2)^n -(x+1)^n) - ((x+1)^n-x^n)$ $=(x+2)^n-2(x+1)^n +x^n$ ...etc.

I think $\Delta^n y = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} (x+k)^n$. This sum is the same as $\sum_{k=0}^{n} (-1)^{n-k}\binom{n}{k}\sum_{s=0}^{n} \binom{n}{s}x^s k^{n-s}$ after using the binomial formula for $(x+k)^n$. I haven't been able to show that this is $n!$. If it is then only the constant term ($s=0$), $\sum_{k=0}^{n} (-1)^k\binom{n}{k}k^n$ should remain and this should be n!.

Does anyone know if this is right and if so how to show it?

$\Delta^{n+1} y = n!-n!=0$ so this part of the statement is fine.

Answer 1

Hint: Notice that $\Delta^k (x^n)$ is a polynomial of degree $n-k$, because the highest order term in $x$ cancels out with each application of $\Delta$ (of course you should prove this). So for $\Delta^n (x^n)$ what you have to show is that all that will be left is the constant term.

Answer 2

For $k>0$ it’s not hard to check that

$$\Delta(x^k)=\sum_{i=0}^{k-1}\binom{k}ix^i=kx^{k-1}+p_k(x)\;,\tag{1}$$

where $p_k(x)$ is a polynomial of degree at most (in fact exactly) $k-2$. Since $\Delta$ is easily seen to be a linear operator, it follows immediately that if $p(x)$ is any non-zero polynomial, $\Delta(p(x))$ is a polynomial, and $\deg\Delta(p(x))=\deg p(x)-1$. By an easy induction it then follows that $\Delta^n(x^n)$ is a constant and that $\Delta^n(x^k)=0$ if $n>k$. Applying that last fact to $(1)$, we see that

$$\Delta^k(x^k)=\Delta^{k-1}\big(\Delta(x^k)\big)=k\Delta^{k-1}(x^{k-1})+\Delta^{k-1}(p_k(x))=k\Delta^{k-1}(x^{k-1})\;.$$

Now just use induction to finish the argument.