Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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;

It is also known as Leibniz formula

share|cite|improve this question
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 . – 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$).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.