2

For the proof of the expanded divided differences formula, I learned how to use induction.

Expanded form:

\begin{aligned}f[x_{0}]&=f(x_{0})\\f[x_{0},x_{1}]&={\frac {f(x_{0})}{(x_{0}-x_{1})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})}}\\f[x_{0},x_{1},x_{2}]&={\frac {f(x_{0})}{(x_{0}-x_{1})\cdot (x_{0}-x_{2})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})\cdot (x_{1}-x_{2})}}+{\frac {f(x_{2})}{(x_{2}-x_{0})\cdot (x_{2}-x_{1})}}\\f[x_{0},x_{1},x_{2},x_{3}]&={\frac {f(x_{0})}{(x_{0}-x_{1})\cdot (x_{0}-x_{2})\cdot (x_{0}-x_{3})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})\cdot (x_{1}-x_{2})\cdot (x_{1}-x_{3})}}+{\frac {f(x_{2})}{(x_{2}-x_{0})\cdot (x_{2}-x_{1})\cdot (x_{2}-x_{3})}}+\\&\quad \quad {\frac {f(x_{3})}{(x_{3}-x_{0})\cdot (x_{3}-x_{1})\cdot (x_{3}-x_{2})}}\\f[x_{0},\dots ,x_{n}]&=\sum _{j=0}^{n}{\frac {f(x_{j})}{\prod _{k\in \{0,\dots ,n\}\setminus \{j\}}(x_{j}-x_{k})}}\end{aligned}

I was wondering if we could prove the formula directly without induction. Any ideas?

Hoda Bibo
  • 405
  • What do you mean by "proving the formula"? These formulas are the definition of Newton's divided differences. – Fernando Chu Jun 20 '20 at 05:46
  • As @Shiranai points out, there really is no proof. What you may want is the derivation of the formula. This can be found through a quick google. – David Jun 20 '20 at 05:51
  • Go through this link. Hope you'll get answer. Little bit of trignometry will help which is not mentioned in this article. – AxyuS Jun 20 '20 at 05:53
  • @Shiranai https://math.stackexchange.com/questions/95585/expanded-form-of-divided-differences – Hoda Bibo Jun 20 '20 at 05:57
  • @David the proof of the alternative definition is here: https://math.stackexchange.com/questions/95585/expanded-form-of-divided-differences I wanted to know if we can prove it without induction – Hoda Bibo Jun 20 '20 at 05:58
  • @Axyus yes, that's induction. So I think we can only use induction....thank you :) – Hoda Bibo Jun 20 '20 at 06:04
  • There was nothing wrong with your original question and therefore no need to delete it. Regular users have favorite tags that they monitor. Therefore there is no need to repost the same question to get to front of the line. In fact, this practice is frowned upon. I imagine that the modified form of the Lagrange interpolation polynomial is the key to a direct proof. – Carl Christian Jun 20 '20 at 13:46
  • @Carl Christian that's not why I deleted the question, some users closed my post instead of helping me to find what detail I should have added. I got a message that said I should either repost the question with more details or edit the post. So I deleted my post.....unfortunately people who can't guide you just close your post! – Hoda Bibo Jun 20 '20 at 14:48
  • My apologies. I was sure that it had been re-opened after you added the expanded form which I found was sufficient. – Carl Christian Jun 20 '20 at 19:32
  • @Carl Christian, no need to apologize. Thank you for guiding me and giving me the hint! It worked – Hoda Bibo Jun 21 '20 at 11:58
  • You are very welcome. I was very happy to visit the expanded form. It is a good way to see that the divided difference $f[x_0,x_1,\dotsc,x_n]$ is a differentiable function of the (distinct) nodes $(x_1,\dotsc,x_n)$. – Carl Christian Jun 21 '20 at 12:49

1 Answers1

1

A direct proof is possible using the Lagrange form of the interpolation polynomial.

Let $x_0,x_1,\dotsc,x_n$ denote $n+1$ distinct nodes and let $f$ denote a real function defined on the nodes. Let $p$ denote the polynomial of degree at most $n$ which interpolates $f$ at the nodes. Then the Lagrange form of $p$ is the familiar expression $$p(x) = \sum_{j=0}^n f(x_j)\prod_{i\not=j} \frac{x-x_i}{x_j-x_i}.$$ Now the divided difference $f[x_0,x_1,\dotsc,x_n]$ is the coefficient of $x^n$ in $p$. This can either be taken as the definition of the divided differences or derived as a separate result from, say, the recursive definition of the divided differences. In either case the structure of $p$ reveals that $$ f[x_0,x_1,\dotsc,x_n] = \sum_{j=0}^n \frac{f(x_j)}{\prod_{i\not=j} (x_j-x_i)}. $$ This completes the proof.

Carl Christian
  • 12,583
  • 1
  • 14
  • 37