Using Newton's Divided Difference formula, prove that
$$f(x) = f(0) + x\,\Delta f(-1) +\frac{x(x+1)}{2!} \, \Delta^2f(-1) + \frac{(x+1)(x)(x-1)}{3!} \, \Delta^3f(-2)+ \cdots$$
where $\Delta$ is forward difference operator
Now i know that Newton's divided formula, but how do i prove above formula using that?
Thanks for helping me out
We will show the validity of OP's expression in two steps.
At first we derive a representation of Newton's divided difference formula based upon operators which is convenient for further transformations.
The second step is iteratively applying a representation of the identity operator in order to do proper rearrangements.
In the following we need three operators, the identity operator $I$ which leaves a function unchanged, the shift operator $E$, defined pointwise on a function by shifting the argument by $1$ and the difference operator $\Delta$, also defined pointwise. We get \begin{align*} If&=f\\ Ef(x)&=f(x+1)\\ \Delta f(x)&=f(x+1)-f(x) \end{align*} We also need a generalisation of the shift operator $E^a$ with $E^af(x)=f(x+a)$. Since $\Delta f(x)=f(x+1)-f(x)=Ef(x)-If(x)=(E-I)f(x)$ we get the fundamental relationship \begin{align*} \Delta = E-I \qquad\text{resp.}\qquad E=I+\Delta\tag{1}\\ \end{align*}
First step: Operator representation of Newton's Divided Difference formula
We look at the first few entries of $f(x_0),\ldots,f(x_n)$ and transform the formulas using operators. In order to do so, we make following
Assumption: The interpolation points $x_0,\ldots,x_n$ are equidistant with $\Delta x_k=x_{k+1}-x_k=1$, with $0\leq k \leq n-1$.
$$ $$
At first we analyse a case with small $n=4$ \begin{array}{ll} f(x_0)=f(x_0)=If(x_0)&\qquad \frac{f(x_1)-f(x_0)}{x_1-x_0}=Ef(x_0)-If(x_0)=(E-I)f(x_0)\\ f(x_1)=f(x_0+1)=Ef(x_0)&\qquad \frac{f(x_2)-f(x_1)}{x_2-x_1}=E^2f(x_0)-Ef(x_0)=E(E-I)f(x_0)\\ f(x_2)=f(x_0+2)=E^2f(x_0)&\qquad \frac{f(x_3)-f(x_2)}{x_3-x_2}=E^3f(x_0)-E^2f(x_0)=E^2(E-I)f(x_0)\\ f(x_3)=f(x_0+3)=E^3f(x_0)&\qquad \frac{f(x_4)-f(x_3)}{x_4-x_3}=E^4f(x_0)-E^3f(x_0)=E^3(E-I)f(x_0)\\ f(x_4)=f(x_0+4)=E^4f(x_0)&\\ \end{array}
$$ $$
The next differences are \begin{array}{l} \frac{\frac{f(x_2)-f(x_1)}{x_2-x_1}-\frac{f(x_1)-f(x_0)}{x_1-x_0}}{x_2-x_0}=\frac{1}{2}\left(E(E-I)-I(E-I)\right)f(x_0)= \frac{1}{2}(E-I)^2f(x_0)\\ \frac{\frac{f(x_3)-f(x_2)}{x_3-x_2}-\frac{f(x_2)-f(x_1)}{x_2-x_1}}{x_3-x_1}=\frac{1}{2}\left(E^2(E-I)-E(E-I)\right)f(x_0)= \frac{1}{2}E(E-I)^2f(x_0)\\ \frac{\frac{f(x_4)-f(x_3)}{x_4-x_3}-\frac{f(x_3)-f(x_2)}{x_3-x_2}}{x_4-x_2}=\frac{1}{2}\left(E^3(E-I)-E^2(E-I)\right)f(x_0)= \frac{1}{2}E^2(E-I)^2f(x_0)\\ \end{array} Note, the factor $\frac{1}{2}$ corresponds to $\frac{1}{x_{m+2}-x_m}$ and further steps with $\frac{1}{x_{m+k}-x_m}$ contribute a factor $\frac{1}{k}$ this way. The next differences are already much more conveniently described with operators \begin{align*} \frac{1}{3}&\left(\frac{1}{2}E(E-I)^2f(x_0)-\frac{1}{2}(E-I)^2f(x_0)\right)=\frac{1}{3!}(E-I)^3f(x_0)\\ \frac{1}{3}&\left(\frac{1}{2}E^2(E-I)^2f(x_0)-\frac{1}{2}E(E-I)^2f(x_0)\right)=\frac{1}{3!}E(E-I)^3f(x_0)\\ \end{align*} and the last difference is obviously \begin{align*} \frac{1}{4!}(E-I)^4f(x_0) \end{align*}
We conclude the interpolation polynomial with equidistant points $x_0,\ldots,x_4$ and $\Delta x_k=1$ has the form
\begin{align*} If(x_0)&+x(E-I)f(x_0)+\frac{1}{2}x(x-1)(E-I)^2f(x_0)\\ &\qquad+\frac{1}{3!}x(x-1)(x-2)(E-I)^3f(x_0)\\ &\qquad+\frac{1}{4!}x(x-1)(x-2)(x-3)(E-I)^4f(x_0)\\ &=\sum_{k=0}^{4}\binom{x}{k}(E-I)^kf(x_0)\\ &=\sum_{k=0}^{4}\binom{x}{k}\Delta^kf(x_0)\tag{2} \end{align*} Note, the last step (2) uses the relation (1) and binomial coefficients as convenient notation.
Since (2) is obviously related to the binomial series we change the point of view and consider the formal operator series
\begin{align*} E^x=\sum_{k=0}^{\infty}\binom{x}{k}\Delta^k\tag{3} \end{align*}
Note, that (3) is a purely formal operator equation. There is no occurrence of a function $f$ and there is also a shift of the meaning of $x$, which is no longer treated as variable but instead as operator. The meaning of the operator $x$ when applied to a function $f$ is simply multiplication with $x$.
The equation (3) is the representation of Newton's interpolation polynomials based upon Newton's divided difference formula. We obtain with $x_0=0$ \begin{align*} f(x)&=E^xf(0)=\sum_{k=0}^{\infty}\binom{x}{k}\Delta^kf(0)\tag{4}\\ &=f(0)+\binom{x}{1}\Delta f(0)+\frac{1}{2!}\binom{x}{2}\Delta ^2f(0)+\frac{1}{3!}\binom{x}{3}\Delta ^3f(0)+\cdots \end{align*}
$$ $$
Second step: Rearrangement of the operator representation
Since we have derived an operator representation, we will now rearrange it without changing it by applying the Identity operator $I$ in a specific manner.
The following is valid \begin{align*} E^{-1}(I+\Delta)=I \end{align*} since \begin{align*} E^{-1}(I+\Delta)f(x)&=E^{-1}(If(x)+\Delta f(x))\\ &=E^{-1}f(x)+E^{-1}(f(x+1)-f(x))\\ &=f(x-1)+f(x)-f(x-1)\\ &=f(x) \end{align*} Note, that the difference operator $\Delta$ and the shift operator $E^a$ commute, since \begin{align*} \Delta E^a f(x)&=\Delta f(x+a)\\ &=f(x+a+1)-f(x+a)\\ &= E^a f(x+1)- E^a f(x)\\ &=E^a \left(f(x+1) - f(x)\right)\\ &= E^a \Delta f(x)\\ \end{align*}
We are ready for the rearrangement. We leave the first member of the series in (4) unchanged and apply the identity operator $I=E^{-1}(I+\Delta)$ to the other part. \begin{align*} f(x)&=\sum_{k=0}^{\infty}\binom{x}{k}\Delta^kf(0)\\ &=f(0)+\sum_{k=1}^{\infty}\binom{x}{k}\Delta^kIf(0)\\ &=f(0)+\sum_{k=1}^{\infty}\binom{x}{k}\Delta^kE^{-1}(I+\Delta)f(0)\tag{5}\\ &=f(0)+\sum_{k=1}^{\infty}\binom{x}{k}\left(\Delta^k+\Delta^{k+1}\right)E^{-1}f(0)\tag{6}\\ &=f(0)+\sum_{k=0}^{\infty}\binom{x}{k+1}\Delta^{k+1}E^{-1}f(0) +\sum_{k=1}^{\infty}\binom{x}{k}\Delta^{k+1}E^{-1}f(0)\tag{7}\\ &=f(0)+\binom{x}{1}\Delta E^{-1}f(0)+\sum_{k=1}^{\infty}\binom{x+1}{k+1}\Delta^{k+1}E^{-1}f(0)\tag{8}\\ &=f(0)+\binom{x}{1}\Delta E^{-1}f(0)+\binom{x+1}{2}\Delta^2 E^{-1}f(0)\\ &\qquad\qquad+\sum_{k=2}^{\infty}\binom{x+1}{k+1}\Delta^{k+1}E^{-1}f(0)\tag{9}\\ &=f(0)+x\Delta f(-1)+\frac{1}{2}(x+1)x\Delta^2 f(-1)\\ &\qquad\qquad+\sum_{k=2}^{\infty}\binom{x+1}{k+1}\Delta^{k+1}E^{-1}f(0)\tag{10}\\ \end{align*}
Comment:
In (5) we use the relation $I=E^{-1}(I+\Delta)$
In (6) we use the commutativity of the operators $E^a$ and $\Delta$
In (7) we shift the index in the first sum
In (8) we extract the summand with $k=0$ and use the relationship $\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}$
In (9) we extract the summand with $k=1$
In (10) we apply the shift operator to $E^{-1}$ to $f(0)$
Observe, that we could derive in (10) the first three summands of OPs expression. Now we apply again the identity operator to the series starting with $k=2$.
\begin{align*} \sum_{k=2}^{\infty}&\binom{x+1}{k+1}\Delta^{k+1}E^{-1}(I+\Delta)E^{-1}f(0)\\ &=\sum_{k=2}^{\infty}\binom{x+1}{k+1}\left(\Delta^{k+1}+\Delta^{k+2}\right)E^{-2}f(0)\\ &=\sum_{k=1}^{\infty}\binom{x+1}{k+2}\Delta^{k+2}E^{-2}f(0)+\sum_{k=2}^{\infty}\binom{x+1}{k+1}\Delta^{k+2}E^{-2}f(0)\\ &=\binom{x+1}{3}\Delta^{3}E^{-2}f(0)+\sum_{k=2}^{\infty}\binom{x+2}{k+2}\Delta^{k+2}E^{-2}f(0)\\ &=\binom{x+1}{3}\Delta^{3}E^{-2}f(0)+\binom{x+2}{4}\Delta^{4}E^{-2}f(0)+\sum_{k=3}^{\infty}\binom{x+2}{k+2}\Delta^{k+2}E^{-2}f(0)\\ &=\frac{1}{3!}(x+1)x(x-1)\Delta^{3}f(-2)+\frac{1}{4!}(x+2)(x+1)x(x-1)\Delta^{4}f(-2)\\ &\qquad+\sum_{k=3}^{\infty}\binom{x+2}{k+2}\Delta^{k+2}E^{-2}f(0)\tag{11}\\ \end{align*}
Collecting (10) and (11) we obtain
\begin{align*} f(x)&=f(0)+x\Delta f(-1)+\frac{1}{2}(x+1)x\Delta^2 f(-1)\\ &\qquad+\frac{1}{3!}(x+1)x(x-1)\Delta^{3}f(-2)+\frac{1}{4!}(x+2)(x+1)x(x-1)\Delta^{4}f(-2)\\ &\qquad+\sum_{k=3}^{\infty}\binom{x+2}{k+2}\Delta^{k+2}E^{-2}f(0)\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{align*} and OP's claim follows by iteratively applying this method.
Note: A similar derivation of step 2 called Interpolation by the Gauss series is presented in chapter 7, paragraph 127 in C. Jordans classic Calculus of finite differences.
