7
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ You should explain what $\Delta$ means in this context. I think I know what is meant, but it would still help. $\endgroup$ – Ian Aug 31 '15 at 16:30
  • $\begingroup$ I took a bit of a liberty in changing $\bigtriangleup$ to $\Delta$, but I also put a small space before it, so instead of $A\Delta B$ you see $A\,\Delta B$. This is not a binary operator and should not have such a space on both sides. If it referred to a symmetric difference, I'd put a space on both sides, just by writing \mathbin{\Delta}. ${}\qquad{}$ $\endgroup$ – Michael Hardy Aug 31 '15 at 17:06
  • $\begingroup$ @MichaelHardy Thanks $\endgroup$ – Taylor Ted Aug 31 '15 at 18:53
7
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @TaylorTed: Thanks for accepting my answer and granting the bounty! :-) Best regards, $\endgroup$ – Markus Scheuer Sep 7 '15 at 9:09

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.