Newton polynomial divided differences When trying to interpolate data points $(t_i,y_i)$, one can use Newton's polynomials which are spanned by the basis of $P_{n-1}$ given by polynomials of the form
$$ t-t_1, (t-t_1)(t-t_2), ..., \prod_{j=1}^{n-1} (t-t_j) $$
So, in the newton basis, an interpolant looks as 
$$ \phi_{n-1}(t) = \alpha_1 + \alpha_2(t-t_1) + ... + \alpha_n (t-t_1)(t-t_2)...(t-t_{n-1})$$
now, one can do $\phi_{n-1}(t_i) = y_i $ to find $\alpha_i$ which requires to solve a lower triangular matrix.
Now, if we introduce the notion of divided differences,
$$ f[t_k] = y_k, f[t_1,t_2,...,t_k] = \frac{ f[t_2,t_3,...,t_k] - f[t_1,t_2,...,t_{k-1}] }{t_k-t_1} $$
observe that 
$$ \phi_{n-1}(t_1) = \alpha_1 = y_1 = f[t_1] $$
Also,
$$ \phi_{n-1}(t_2) = \alpha_1 + \alpha_2 (t_2 - t_1) = y_2 $$
since $\alpha_1 = y_1$, we observe that $\alpha_2 = \dfrac{ y_2 - y_1 }{t_2 - t_1} = \dfrac{ f[t_2]-f[t_1]}{t_2-t_1}  = f[t_1,t_2]$
So, we can claim that in general, $\alpha_k = f[t_1,...,t_k]$. Im trying to prove this by induction but I dont see a plan on how to use the induction hypothesis to check for $\alpha_{k+1}$. We can assume that result holds for $k$ so that we can write the interpolant $\phi_k(t)$ as
$$ \phi_k(t) = f[t_1] + f[t_1,t_2](t-t_1) + ..+ f[t_1,...,t_k] (t-t_1)...(t-t_{k-1}) + \alpha_{k+1} (t-t_1)...(t-t_{k}) $$
but, then how can we take from there?
 A: The subject is better caught using a matricial reperesentation, and
it is preferrable to index from $0$, as it provides a neater handling of the sums and products.
Given an assigned sequence $\left\{ {t_{\,0} ,t_{\,1} , \cdots ,t_{\,h} , \cdots } \right\}\quad \left| {\;t_{\,k}  \ne t_{\,j} } \right.$,
  let's indicate by $\pi _{\,n} (t)$ the $n$-th degree polynomial
$$
\pi _{\,n} (x,{\bf t}) = \prod\limits_{0\, \le \,j\, \le \,n-1} {\left( {x - t_{\,j} } \right)} 
$$
so that, with the convention of the null product, we have
$$
\pi _{\,0} (x,{\bf t}) = 1\quad \pi _{\,1} (x,{\bf t}) = \left( {x - t_{\,0} } \right)\quad  \cdots 
$$
We want to construct a polynomial of degree $h$ such that at the $h+1$ points $(t_0, \cdots,t_h)$
it takes the values $(f_0, \cdots,f_h)$, that is
$$
p_{\,h} \left( {x,{\bf t},{\bf f}} \right)\;:\;\;p_{\,h} \left( {t_{\,k} ,{\bf t},{\bf f}} \right) = f_{\,k} \quad \left| {\,0 \le k \le h} \right.
$$
While we could express it in terms of Lagrange polynomials, we want instead
to express it as a linear combination of the $\pi _{\,k} (x,{\bf t})$ polynomials
$$
\eqalign{
  & p_{\,h} \left( {x,{\bf t},{\bf f}} \right) = \left( {\matrix{
   {\pi _{\,0} (x,{\bf t})} & {\pi _{\,1} (x,{\bf t})} &  \cdots  & {\pi _{\,h} (x,{\bf t})}  \cr 
 } } \right)\left( {\matrix{   {\beta _{\,0} }  \cr    {\beta _{\,1} }  \cr     \vdots   \cr    {\beta _{\,h} }  \cr  } } \right) =   \cr 
  &  = \overline {{\bf \pi }_{\,h} } (x,{\bf t})\;{\bf \beta }_{\,h}  \cr} 
$$
note that the vector ${\bf \pi }$ includes polynomials of varying degree.
Since the above holds for whichever value of $x$, it shall hold in particular for each $x=t_k$,
and we get the LT matrix equation you already know
$$ \bbox[lightyellow] {  
\eqalign{
  & \left( {\matrix{   {f_{\,0} }  \cr    {f_{\,1} }  \cr     \vdots   \cr    {f_{\,h} }  \cr  } } \right)
 = \left( {\matrix{
   1 & 0 &  \cdots  & 0  \cr 
   1 & {\left( {t_1  - t_0 } \right)} &  \cdots  & 0  \cr 
    \vdots  &  \vdots  &  \ddots  &  \vdots   \cr 
   1 & {\prod\limits_{0\, \le \,j\, \le \,0} {\left( {t_h  - t_{\,j} } \right)} } &  \cdots  & {\prod\limits_{0\, \le \,j\, \le \,h - 1} {\left( {t_h  - t_{\,j} } \right)} }  \cr 
 } } \right)\left( {\matrix{   {\beta _{\,0} }  \cr    {\beta _{\,1} }  \cr     \vdots   \cr    {\beta _{\,h} }  \cr  } } \right) =   \cr 
  &  = {\bf f} = {\bf P}({\bf t})\;{\bf \beta } \cr} 
}\tag{1}$$
Consider now that the Divided Difference of a sequence $y_k$ wrt $x_k$
$$
\left\{ \matrix{
  \left[ {y_{\,q} } \right] = y_{\,q}  \hfill \cr 
  \left[ {y_{\,q} ,\, \ldots ,\,y_{\,q + n} } \right]
 = {{\left[ {y_{\,q + 1} ,\, \ldots ,\,y_{\,q + n} } \right] - \left[ {y_{\,q} ,\, \ldots ,\,y_{\,q + n - 1} } \right]} \over {x_{\,q + n}  - x_{\,q} }} \hfill \cr}  \right.
$$
can be expressed as a linear combination of the $y_k$ values as follows
$$ \bbox[lightyellow] {  
\left[ {y_{\,q} ,\, \ldots ,\,y_{\,q + n} } \right]
 = \sum\limits_{0\, \le \,m\, \le \,n} {{{y_{m + q} } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m + q}  - x_{\,k + q} } \right)} }}} 
}\tag{2}$$
because in fact, taking $q=0$ wlog, it is
$$
\eqalign{
  & \left[ {y_{\,1} ,\, \ldots ,\,y_{\,n + 1} } \right] - \left[ {y_{\,0} ,\, \ldots ,\,y_{\,n} } \right] =   \cr 
  &  = \sum\limits_{0\, \le \,m\, \le \,n} {{{y_{m + 1} } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m + 1}  - x_{\,k + 1} } \right)} }}}
  - \sum\limits_{0\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m}  - x_{\,k} } \right)} }}}  =   \cr 
  &  = \sum\limits_{1\, \le \,m + 1\, \le \,n + 1} {{{y_{m + 1} } \over {\prod\limits_{1\, \le \,k + 1\, \ne \,m + 1\, \le \,n + 1} {\left( {x_{\,m + 1}
  - x_{\,k + 1} } \right)} }}}  - \sum\limits_{0\, \le \,m\, \le \,n} {{{y_m }
 \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m}  - x_{\,k} } \right)} }}}  =   \cr 
  &  = \sum\limits_{1\, \le \,m\, \le \,n + 1} {{{y_m } \over {\prod\limits_{1\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m}  - x_{\,k} } \right)} }}}
  - \sum\limits_{0\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m}  - x_{\,k} } \right)} }}}  =   \cr 
  &  = \sum\limits_{1\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{1\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m}  - x_{\,k} } \right)} }}}
  + {{y_{n + 1} } \over {\prod\limits_{1\, \le \,k\, \le \,n} {\left( {x_{\,n + 1}  - x_{\,k} } \right)} }}
 - {{y_0 } \over {\prod\limits_{1\, \le \,k\, \le \,n} {\left( {x_{\,0}  - x_{\,k} } \right)} }}
 - \sum\limits_{1\, \le \,m\, \le \,n} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m}  - x_{\,k} } \right)} }}}  =   \cr 
  &  =  - {{y_0 } \over {\prod\limits_{1\, \le \,k\, \le \,n} {\left( {x_{\,0}  - x_{\,k} } \right)} }}
 + \sum\limits_{1\, \le \,m\, \le \,n} {y_m \left( {{1 \over {\prod\limits_{1\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m}  - x_{\,k} } \right)} }}
 - {1 \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m}  - x_{\,k} } \right)} }}} \right)}
  + {{y_{n + 1} } \over {\prod\limits_{1\, \le \,k\, \le \,n} {\left( {x_{\,n + 1}  - x_{\,k} } \right)} }} =   \cr 
  &  =  - {{\left( {x_{\,0}  - x_{\,n + 1} } \right)y_0 } \over {\prod\limits_{1\, \le \,k\, \le \,n + 1} {\left( {x_{\,0}  - x_{\,k} } \right)} }}
 + \sum\limits_{1\, \le \,m\, \le \,n} {y_m \left( {{{\left( {x_{\,m}  - x_{\,0} } \right)} \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n + 1}
 {\left( {x_{\,m}  - x_{\,k} } \right)} }} - {{\left( {x_{\,m}  - x_{\,n + 1} } \right)} \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n + 1} {\left( {x_{\,m}
  - x_{\,k} } \right)} }}} \right)}  + {{\left( {x_{\,n + 1}  - x_{\,0} } \right)y_{n + 1} } \over {\prod\limits_{0\, \le \,k\, \le \,n}
 {\left( {x_{\,n + 1}  - x_{\,k} } \right)} }} =   \cr 
  &  = \left( {x_{\,n + 1}  - x_{\,0} } \right)\sum\limits_{0\, \le \,m\, \le \,n + 1} {{{y_m } \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n + 1}
 {\left( {x_{\,m}  - x_{\,k} } \right)} }}}  =   \cr 
  &  = \left( {x_{\,n + 1}  - x_{\,0} } \right)\left[ {y_{\,0} ,\, \ldots ,\,y_{\,n + 1} } \right] \cr} 
$$
Therefore, in matrix notation we will have
$$ \bbox[lightyellow] {  
\eqalign{  & \left( {\matrix{   {\left[ {f_{\,0} } \right]}  \cr    {\left[ {f_{\,0} ,f_{\,1} } \right]}  \cr     \vdots   \cr    {\left[ {f_{\,0} , \ldots ,f_{\,h} } \right]}
  \cr  } } \right)
 = \left( {\matrix{
   1 & 0 &  \cdots  & 0  \cr 
   {{1 \over {\left( {t_{\,0}  - t_{\,1} } \right)}}} & {{1 \over {\left( {t_{\,1}  - t_{\,0} } \right)}}} &  \cdots  & 0  \cr 
    \vdots  &  \vdots  &  \ddots  &  \vdots   \cr 
   {{1 \over {\prod\limits_{0\, \le \,k\, \ne \,0\, \le \,h} {\left( {t_{\,0}  - t_{\,k} } \right)} }}} & {{1 \over {\prod\limits_{0\, \le \,k\, \ne \,1\, \le \,h}
 {\left( {t_{\,1}  - t_{\,k} } \right)} }}} &  \cdots  & {{1 \over {\prod\limits_{0\, \le \,k\, \ne \,h\, \le \,h} {\left( {t_{\,h}  - t_{\,k} } \right)} }}}  \cr  } } \right)
\left( {\matrix{   {f_{\,0} }  \cr    {f_{\,1} }  \cr     \vdots   \cr    {f_{\,h} }  \cr  } } \right) =   \cr 
  &  = {\bf D}_{\,{\bf div}} ({\bf t})\;{\bf f} \cr} 
}\tag{3}$$
The crucial point is that
$$ \bbox[lightyellow] {  
{\bf D}_{\,{\bf div}} ({\bf t}) = {\bf P}({\bf t})^{\, - \,{\bf 1}} 
}\tag{4}$$
which in connection with (1) demonstrates the thesis.   
In fact
$$
\eqalign{
  & \left[ {y_{\,0} ,\, \ldots ,\,y_{\,n} } \right]\quad \left| {\;y = f(x) = \prod\limits_{0\, \le \,j\, \le \,g - 1} {\left( {x - x_{\,j} } \right)} } \right.\quad  =   \cr 
  &  = \sum\limits_{0\, \le \,m\, \le \,n} {{{f\left( {x_m } \right)} \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m}  - x_{\,k} } \right)} }}}  =   \cr 
  &  = \left[ {g \le n} \right]\sum\limits_{g\, \le \,m\, \le \,n} {{{f\left( {x_m } \right)}
 \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m}  - x_{\,k} } \right)} }}}  =   \cr 
  &  = \left[ {g \le n} \right]\sum\limits_{g\, \le \,m\, \le \,n} {{{\prod\limits_{0\, \le \,j\, \le \,g - 1} {\left( {x_{\,m}  - x_{\,j} } \right)} }
 \over {\prod\limits_{0\, \le \,k\,\, \le \,g - 1} {\left( {x_{\,m}  - x_{\,k} } \right)}
 \prod\limits_{g\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m}  - x_{\,k} } \right)} }}}  =   \cr 
  &  = \left[ {g \le n} \right]\sum\limits_{g\, \le \,m\, \le \,n} {{1 \over {\prod\limits_{g\, \le \,k\, \ne \,m\, \le \,n} {\left( {x_{\,m}  - x_{\,k} } \right)} }}}  =   \cr 
  &  = \left[ {g \le n} \right]\sum\limits_{0\, \le \,m\, \le \,n - g} {{1 \over {\prod\limits_{0\, \le \,k\, \ne \,m\, \le \,n - g}
 {\left( {x_{\,m + g}  - x_{\,k + g} } \right)} }}}  =   \cr 
  &  = \left[ {g \le n} \right]\left[ {1_{\,g} ,\, \ldots ,\,1_{\,g + \left( {n - g} \right)} } \right] = \left[ {g = n} \right] \cr} 
$$
where  the second step follows from being $f(x_m)=0$ for $m<g$
and where $[g \le n],\,[g = n]$ denotes the Iverson bracket.
A: I would like to show how the missing induction step can be carried out. We have $n+1$ distinct nodes $x_0, x_1, \dotsc, x_n$. Let $p$ denote the polynomial of degree at most $n-1$ which interpolates $f$ at the first $n$ nodes, i.e., $x_0, x_1, \dotsc x_{n-1}$. Then by our induction hypothesis $$p(x) = f[x_0,x_1,\dotsc,x_{n-1}] x^{n-1} + r(x)$$
where $r$ is a polynomial of degree at most $n-2$. Let $q$ denote the polynomial of degree at most $n-1$ which interpolates $f$ at the last $n$ nodes, i.e., $x_1, x_2, \dotsc x_n$. Then by our induction hypothesis
$$q(x) = f[x_1,x_2,\dotsc,x_n] x^{n-1} + s(x)$$
where $s$ is a polynomial of degree at most $n-2$. Now, consider the polynomial $t$ given by 
$$t(x) = p(x)\frac{x_n-x}{x_n-x_0} + q(x)\frac{x-x_0}{x_n-x_0}$$
I claim that $t$ is unique polynomial which interpolates $f$ at all $n+1$ nodes. We have $$ t(x_0) = p(x_0) \cdot 1 + q(x_0) \cdot 0 = p(x_0) = f(x_0),$$
because $p$ interpolates $f$ at $x_0$. We have 
$$ t(x_n) = p(x_n) \cdot 0 + q(x_n) \cdot 1 = q(x_n) = f(x_n),$$
because $q$ interpolates $f$ at $x_n$. For $1<i<n$ we have
$$ t(x_i) = q(x_i)\left(\frac{x_n-x_i}{x_n-x_0}\right) + q(x_i)\left(\frac{x_i-x_0}{x_n-x_0}\right) = f(x_i) \frac{(x_n-x_i) + (x_i-x_0)}{x_n-x_0} = f(x_i),$$
because $p$ and $q$ both interpolate $f$ at $x_i$. This shows that $t$ is the polynomial of degree at most $n$ which interpolates $f$ at the $n+1$ nodes. We have 
$$t(x) = c_n t^n + u(x)$$
where $c_n$ is a constant and $u$ is a polynomial of degree at most $n-1$. The formula for $c_n$ follows readily from the expressions for $p$, $q$ and $t$. We have
\begin{align} t(x) &= \frac{\Big(f[x_1,x_2,\dotsc,x_n]x^{n-1} +r(x)\Big)(x-x_0) - \Big(f[x_0,x_1,\dotsc,x_{n-1}]x^{n-1}+s(x)\Big)(x-x_n)}{x_n-x_0} \\ &= \left(\frac{f[x_1,x_2,\dotsc,x_n]-f[x_0,x_1,\dotsc,x_{n-1}]}{{x_n-x_0}} \right) x^n + \text{lower order terms.} \end{align}
We see that the choice of 
$$ f[x_0,x_1,\dots,x_n] = \frac{f[x_1,x_2,\dotsc,x_n]-f[x_0,x_1,\dotsc,x_{n-1}]}{{x_n-x_0}}$$
is exactly what is needed to complete our induction step.
 The construction of $t$ in terms of $p$ and $q$ is the foundation for Neville's algorithm for evaluating the interpolating polynomial.
