show if $\phi (x) = f(x)g(x)$, this is valid:
$\phi [x_0,x_1,...,x_n]=\sum\limits_{r=0}^n f[x_0,x_1,..,x_r]g[x_r,x_{r+1},...,x_n]$ by induction.

I have tried to prove it by the divided differences formula but things are standing still at the moment.

EDIT: I didn't understand this proof, but you should look at this as a reference; http://www.sosmath.com/CBB/viewtopic.php?t=31735

It is also known as Leibniz formula

  • 1
    $\begingroup$ Can you clarify the notation? Are $\phi,f,g$ polynomials in one variable or in multiple variables? In other words how are $f(x)$ and $f[x_0,...,x_n]$ related? Also is there a difference between the two kinds of brackets you use? $\endgroup$ – Simon Markett Mar 26 '13 at 12:15
  • $\begingroup$ Simon: $f\left[x_0,...,x_n\right]$ is a so-called divided difference of $f$; see en.wikipedia.org/wiki/Divided_differences#Notation . $\endgroup$ – darij grinberg Mar 28 '13 at 1:12

This looks like homework. Therefore, I do not provide the full solution here. But, I want to give anyone with the same problem a good starter.

The problem is to prove Leibniz' formula for divided differences: \begin{align*} (f\cdot g)(x_0,\ldots,x_n) &= \sum_{i=0}^n f(x_0,\ldots,x_i) g(x_i,\ldots,x_n) \end{align*}

The beginning of the induction is very simple: \begin{align*} (f\cdot g)(x_0) = f(x_0) g(x_0) \end{align*}

When you get stuck with the induction step it is always a good idea to carry out one or several induction steps by hand to get the idea:

1st step: \begin{align*} (f\cdot g)(x_0,x_1) &= \frac{(f\cdot g)(x_1) - (f\cdot g)(x_0)}{x_1-x_0}\\ &= \frac{f(x_1)g(x_1) - f(x_0)g(x_0)}{x_1-x_0} \end{align*} We supplement the numerator to get divided differences: \begin{align*} &= \frac{f(x_1)g(x_1) \color{red}{- f(x_1)g(x_0) + f(x_1)g(x_0)} - f(x_0)g(x_0)}{x_1-x_0}\\ &= f(x_1)g(x_0,x_1) + f(x_0,x_1)g(x_0) \end{align*} 2nd step: The assumption of the induction gives: \begin{align*} (fg)(x_0,x_1,x_2) &= \frac{(fg)(x_1,x_2)-(fg)(x_0,x_1)}{x_2-x_0}\\ &= \frac{f(x_1)g(x_1,x_2) + f(x_1,x_2)g(x_2) - f(x_0)g(x_0,x_1) - f(x_0,x_1)g(x_1)}{x_2-x_0} \end{align*} First, we rearrange to group orders of divided differences. \begin{align*} &=\frac{f(x_1)g(x_1,x_2) - f(x_0) g(x_0,x_1) + f(x_1,x_2)g(x_2)-f(x_0,x_1)g(x_1)}{x_2-x_0} \end{align*} Again, supplementing the numerator with mixed terms to get divided differences: \begin{align*} &=\frac{f(x_1)g(x_1,x_2) {\color{red}{- f(x_0)g(x_1,x_2) + f(x_0)g(x_1,x_2)}} - f(x_0) g(x_0,x_1) + f(x_1,x_2)g(x_2) {\color{red}{- f(x_0,x_1)g(x_2) + f(x_0,x_1) g(x_2)}} -f(x_0,x_1)g(x_1)}{x_2-x_0}\\ &=\frac{x_1-x_0}{x_2-x_0}f(x_0,x_1)g(x_1,x_2) + f(x_0)g(x_0,x_1,x_2) + f(x_0,x_1,x_2)g(x_2) + \frac{x_2-x_1}{x_2-x_0}f(x_0,x_1)g(x_1,x_2)\\ &= f(x_0)g(x_0,x_1,x_2)+f(x_0,x_1)g(x_1,x_2) + f(x_0,x_1,x_2)g(x_2) \end{align*}

This should give enough hints to deduce the general induction step. (At least it was sufficient for me to get the idea.)

Note, that you find a nice proof of Leibnitz' formula for divided differences in Chapter I of

Carl de Boor: A Practical Guide to Splines. Springer-Verlag

That proof bases on the multiplication of two polynomials up to degree $n$ that interpolate $f$ and $g$ at $x_0,\ldots,x_n$ in Newton-form. He subtracts the irrelevant polynomial part of the product that vanishes at the sites $x_0,\ldots,x_n$ and considers the coefficient of degree $n$ of remaining part (which is then of highest degree $n$).


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.