3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you, I'll try that. How do you know the constant term left is $n!$? $\endgroup$ – Sam Forbes Apr 2 '13 at 18:47
  • $\begingroup$ I don't. But I think it'll work out, because $\Delta$ is basically just discrete differentiation. $\endgroup$ – Christopher A. Wong Apr 2 '13 at 20:25
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you. This argument seems good and I will try it. It certainly seems like $\Delta$ acts like differentiation like @ChristopherA.Wong mentioned. Just as an extra, does the sum I had for $\Delta^n y$ in my question look ok to you? $\endgroup$ – Sam Forbes Apr 3 '13 at 7:33
  • $\begingroup$ @Sam: You’re welcome. Yes, $\Delta$ does behave a great deal like differentiation; if you can find a copy of Graham, Knuth, & Patashnik, Concrete Mathematics, you can read more about finite calculus in Section $2.6$. Pete L. Clark has a handout with another introduction here. And yes, your summation for $\Delta^ny$ is fine. $\endgroup$ – Brian M. Scott Apr 3 '13 at 18:29
  • $\begingroup$ Thanks for the book info and the link $\endgroup$ – Sam Forbes Apr 7 '13 at 8:13
  • $\begingroup$ @Sam: My pleasure. $\endgroup$ – Brian M. Scott Apr 7 '13 at 18:47

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.