Let $f : [a, b] \rightarrow \mathbb{R}$. Define $$ f[a_0, ..., a_n] := \frac{f[a_1, ..., a_n]-f[a_0, ..., a_{n-1}]}{a_n - a_0} $$ with $f[a]=f(a)$. Consider now $(m + 1)$ distinct nodes $x_j \in \mathbb{R}$ for $j \in \{ 0, \ldots, m \}$. Define the polynomial $$ q_{k+1}(x) = q_k(x) + f[x_0, \ldots, x_{k+1}](x - x_0)(x - x_1)\ldots(x - x_k) $$ with $q_0(x)=f(x_0)$. I want to show that the Lagrange interpolation polynomial of degree $m$, $p_m(x)$, is in fact given by $p_m(x)=q_m(x)$.
How do you show that something is a Lagrange interpolation polynomial? Do you need to show that you can transform into the familiar form of $$ p_m(x) = \sum_{k=0}^{m} L_k(x) \cdot y_k $$ Or, is there any easier method? I have tried induction but I can't unpack the recursive function. Any help would be appreciated.
This is a different approach than the ones in Proof of relation between divided difference and interpolation polynomial coefficient. Possibly unnecessarily complex, but it gets the job done. We will see that the divided difference is the leading coefficient of the Lagrange polynomial, which will let us prove that the two types of polynomials are equal by induction.
Let $\ell[x_0, x_1, \cdots, x_n]$ be the leading coefficient of the Lagrange polynomial which passes through $f$ at $x_0, x_1, \cdots, x_n$. It is easily seen that $$ \ell[x_0, x_1, \cdots, x_n] = \sum_{i=0}^n f(x_i) \prod_{\substack{j=0\\j\neq i}}^n \frac1{x_i - x_j}. $$
We will show that $\ell[x_0, \cdots, x_n] = f[x_0, \cdots, x_n]$. Observe that \begin{align} & \ell[x_0, \cdots, x_n] - \ell[x_1, \cdots, x_{n+1}]\\ =\,& \sum_{i=0}^n f(x_i) \prod_{\substack{j=0\\j\neq i}}^n \frac1{x_i - x_j} - \sum_{i=1}^{n+1} f(x_i) \prod_{\substack{j=1\\j\neq i}}^{n+1} \frac1{x_i - x_j} \\ =\,& f(x_0)\prod_{\substack{j=1}}^n \frac1{x_0 - x_j} + \sum_{i=1}^n f(x_i) \left(\prod_{\substack{j=0\\j\neq i}}^n \frac1{x_i - x_j} - \prod_{\substack{j=1\\j\neq i}}^{n+1} \frac1{x_i - x_j}\right) - f(x_{n+1})\prod_{\substack{j=1}}^n \frac1{x_{n+1} - x_j}\\ =\,& f(x_0)\prod_{\substack{j=1}}^n \frac1{x_0 - x_j} + \sum_{i=1}^n f(x_i) \left(\frac1{x_i - x_0} - \frac1{x_i - x_{n+1}}\right)\prod_{\substack{j=1\\j\neq i}}^n \frac1{x_i - x_j} - f(x_{n+1})\prod_{\substack{j=1}}^n \frac1{x_{n+1} - x_j}\\ =\,& f(x_0)\prod_{\substack{j=1}}^n \frac1{x_0 - x_j} + \sum_{i=1}^n f(x_i) \frac{x_0 - x_{n+1}}{(x_i - x_0)(x_i - x_{n+1})}\prod_{\substack{j=1\\j\neq i}}^n \frac1{x_i - x_j} - f(x_{n+1})\prod_{\substack{j=1}}^n \frac1{x_{n+1} - x_j} \\ =\,& f(x_0)\prod_{\substack{j=1}}^n \frac1{x_0 - x_j} + (x_0 - x_{n+1})\sum_{i=1}^n f(x_i)\prod_{\substack{j=0\\j\neq i}}^{n+1} \frac1{x_i - x_j} - f(x_{n+1})\prod_{\substack{j=1}}^n \frac1{x_{n+1} - x_j} \\ =\,& (x_0 - x_{n+1}) \left( f(x_0)\prod_{\substack{j=1}}^{n+1} \frac1{x_0 - x_j} + \sum_{i=1}^n f(x_i)\prod_{\substack{j=0\\j\neq i}}^{n+1} \frac1{x_i - x_j} + f(x_{n+1})\prod_{\substack{j=0}}^n \frac1{x_{n+1} - x_j} \right) \\ =\,& (x_0 - x_{n+1}) \sum_{i=0}^{n+1} f(x_i)\prod_{\substack{j=0\\j\neq i}}^{n+1} \frac1{x_i - x_j} \\ =\,&(x_0 - x_{n+1}) \ell[x_0, \cdots, x_{n+1}]. \end{align}
Excuse the mess. The idea isn't too complex, it just takes a ton of space to write out in LaTeX. We just showed that $\ell$ satisfies the divided difference recursive formula $$ \ell[x_0, \cdots, x_{n+1}] = \frac{\ell[x_0, \cdots, x_n] - \ell[x_1, \cdots, x_{n+1}]}{x_0 - x_{n+1}}. $$ And since $\ell[x] = f[x] = f(x)$, it must be that $\ell[x_0, \cdots, x_n] = f[x_0, \cdots, x_n]$.
Now we can prove by induction that $q_n$ = $p_n$ for all $n$. For the base case, you can easily verify that $q_0 = p_0$. Now assume that $q_n = p_n$, and consider $$ r(x) = q_n(x) + c \cdot (x - x_0)(x - x_1)\ldots(x - x_n), $$ where $c$ is chosen so that $r(x_{n+1}) = f(x_{n+1})$. (Note that there is one and only one such value of $c$.) Clearly, $r$ is the unique $n+1$ degree polynomial which meets $f$ at $x_0, x_1, \cdots, x_{n+1}$. Thus $r = p_{n+1}$. But since $c$ is the leading coefficient of $r = p_{n+1}$, we have $c = \ell[x_0, \cdots x_{n+1}] = f[x_0, \cdots x_{n+1}]$. Thus $$ p_{n+1}(x) = r(x) = q_n(x) + f[x_0, \cdots x_{n+1}] \cdot (x - x_0)(x - x_1)\ldots(x - x_n) = q_{n+1}(x). $$ This completes the induction.