3

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

pjoltergeist
  • 31
  • 1
  • 3
  • 1
    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? – Simon Markett Mar 26 '13 at 12:15
  • Simon: $f\left[x_0,...,x_n\right]$ is a so-called divided difference of $f$; see http://en.wikipedia.org/wiki/Divided_differences#Notation . – darij grinberg Mar 28 '13 at 01:12

1 Answers1

3

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$).

Tobias
  • 606