2

Prove that the $n$th difference of $x^n$ is $\displaystyle \sum \limits _{i=0}^n(-1)^i\binom{n}{i}(x-i)^n$ (here the first difference is $\Delta (x^n):=(x)^n-(x-1)^n$ and the $n$th difference is defined recursively as $\Delta ^n(x^n):=\Delta ^{n-1}((x)^n)-\Delta ^{n-1}((x-1)^n)$).

I tried using induction, but just proving $\Delta ^n(x^n)$ is given by the indicated formula for all $n$ doesn't seem to work. Instead, I may need a more general formula involving $\Delta ^n(x^m)$, where $m$ and $n$ are positive integers. However, I'm not sure how to come up with this more general formula.

Gord452
  • 1,127
  • 2
  • 9
  • 2
    The pattern is not hard to establish, do $\Delta (x^n), \Delta^2(x^n),...$. – copper.hat Jul 30 '22 at 21:43
  • 1
    @Gord452 FYI, using an [Approach0 search](https://approach0.xyz/search/?q=OR%20content%3A%24%5Csum_%7Bi%3D0%7D%5En(-1)%5Ei%7Bn%5Cchoose%20i%7D(x-i)%5En%24%2C%20OR%20content%3Adifference&p=4), I found the AoPS thread [nth Difference Sequence of nth Powers](https://artofproblemsolving.com/community/c4h1983800p13797464) (in particular, message #$4$), plus quite a few closely related questions on this site, especially [$k$th difference of $1,2^k,3^k,...$](/q/697558/602049). There are many other associated questions, e.g., proving the expression is $n!$, eg., such as at the AoPS thread ... – John Omielan Jul 30 '22 at 21:49
  • 1
    I imagine it should be $(x+i)^n$ above? And $(-1)^i$ should be $(-1)^{n-i}$, I believe. – copper.hat Jul 30 '22 at 21:53
  • 1
    @Gord452 (cont.) [An interesting identity](https://artofproblemsolving.com/community/c6h1733727p11247892), and on this site there's [Binomial Sum: Values](/q/1340837), [Why does this process generate the factorial of the exponent?](/q/2078853), [Repeatedly taking differences on a polynomial yields the factorial of its degree?](/q/2319210), [Expressing a factorial as difference of powers: $\sum_{r=0}^{n}\binom{n}{r}(-1)^r(l-r)^n=n!$?](/q/591350), [Combinatorial proof of $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!$, using inclusion-exclusion](/q/1862571), etc. – John Omielan Jul 30 '22 at 21:55
  • 1
    it remands me https://math.stackexchange.com/questions/4298639/binomial-rule-and-repeatedly-differentiating this question I think differentiating repeatedly (x-i)^n will help – emil agazade Jul 30 '22 at 22:02
  • 1
    It is much more natural to define $\Delta^n$ as $\Delta\circ \Delta^{n-1}$. $(\Delta p)(x)=p(x+1)-p(x), (\Delta^2 p)(x)=p(x+2)-2p(x+1)+p(x), (\Delta^3 p)(x) = p(x+3)-3 p(x+2)+3 p(x+1)-p(x)$ and in general $$(\Delta^n p)(x) = \sum_{k=0}^{n}\binom{n}{k}(-1)^k p(x+n-k)$$ – Jack D'Aurizio Jul 30 '22 at 23:26
  • @JackD'Aurizio for reference this was question B5 of the 1976 putnam exam. An answer I got says the result is $n!$ because it's the nth difference of $x^n$. Is the logic behind that wrong then? – Gord452 Jul 31 '22 at 03:32
  • I am not quite getting the point of the formula, the $n$th difference is $n!$, so why are you focused on the above formula? – copper.hat Jul 31 '22 at 18:23

2 Answers2

2

This problem refers to the backward difference operator \begin{align*} \Delta\left(x^n\right):= x^n-(x-1)^{n} \end{align*} We can prove the formula \begin{align*} \color{blue}{\Delta^n\left(x^n\right)=\sum _{i=0}^n(-1)^i\binom{n}{i}(x-i)^n}\tag{1} \end{align*} using operator methods. We introduce the shift operator $E$ and identity operator $I$ with \begin{align*} Ef(x)&=f(x+1)\\ If(x)&=f(x) \end{align*} We can write the delta operator $\Delta$ as \begin{align*} \color{blue}{\Delta}\left(x^n\right)&=x^n-\left(x-1\right)^n\\ &=I\left(x^n\right)-E^{-1}\left(x^n\right)\\ &=\color{blue}{\left(I-E^{-1}\right)}\left(x^n\right)\tag{2} \end{align*} Since shift operator $E$ and identity operator $I$ are linear operators which commute we obtain according to (2) using the binomial theorem

\begin{align*} \color{blue}{\Delta^n\left(x^n\right)}&=\left(I-E^{-1}\right)^n\left(x^n\right)\\ &=\sum_{i=0}^n\binom{n}{i}(-1)^iE^{-i}I^{n-i}\left(x^n\right)\\ &=\sum_{i=0}^n\binom{n}{i}(-1)^iE^{-i}\left(x^n\right)\\ &\,\,\color{blue}{=\sum_{i=0}^n\binom{n}{i}(-1)^i\left(x-i\right)^n} \end{align*} and the claim (1) follows.

epi163sqrt
  • 102,688
  • 6
  • 95
  • 230
0

Define $(Rf)(x) = f(x)-f(x-1)$. Note that $R$ is linear. It is straightforward using induction to show that $(R^nf )(x) = \sum_{k=0}^n \binom{n}{k} (-1)^k f(x-k)$.

Abusing notation slightly, we see that for any constant $c$ we have $Rc = 0$ and that $Rx^p$ is a polynomial of degree $p-1$ with coefficient $p = \binom{p}{1}$. In particular, $R^n x^n = n!$ and so $ \sum_{k=0}^n \binom{n}{k} (-1)^k (x-k)^n = n!$.

copper.hat
  • 166,869
  • 9
  • 103
  • 245