Prove Lagrange form of interpolation for $x^j$ To interpolate a polynomial of degree $n$ using the Lagrange form, 
$$p(x)=\sum_{i=0}^ny_iL_i(x)$$ with $$L_i(x)=\frac{\prod_{i\not=j}(x-x_j)}{\prod_{i\not=j}(x_i-x_j)}$$
How can I show that for $y_i=x^j_i$ for $j=0, 1, ..., n$ $$\sum_{i=0}^nx_i^jL_i(x)=x^j$$
I read through this question which is the same identity, but the answers were unclear. I tried proving by expanding, so $$p(x)=\sum_{i=0}^n x_i^j \frac{\prod_{i\ne j} (x - x_j)}{\prod_{i \ne j}
  (x_i - x_j)}=\sum_{i=0}^n x_i^j
\frac{(x - x_0)(x - x_1)...(x - x_{i-1})(x - x_{i+1})...(x - x_n)}
{(x_i - x_0)(x_i - x_1)...(x_i - x_{i-1})(x_i - x_{i+1})...(x_i - x_n)}$$ but since the top product has $x$ where the denominator product has $x_i$, nothing seems to cancel out... but if I let $x=x_k$ as suggested in the link would that mean $x_i=x_k$ as well, leaving $\sum x_k^j=x_k^j$?
 A: So we are speaking of "over-interpolation", meaning that we are interpolating $(n+1)$ points laying on a polynomial curve of degree $q$ ($q \le n$)
with a polynomial of higher degree, which then will reduce to having degree $q$.
In fact,  in general, interpolating $n+1$ points will produce a polynomial of degree at most $n$.
$$
p_{\,n} (x) = \sum\limits_{0 \le \,\,i\, \le \,n} {y_{\,i} \frac{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {x - x_{\,j} } \right)} }}{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {x_{\,i}  - x_{\,j} } \right)} }}} \quad  \Rightarrow \quad \deg \left( {p_{\,n} (x)} \right) \le n
$$
and if the points are actually laying on a polynomial of degree <= $n$, we will get exactly that polynomial.
$$
y_{\,i}  = p_{\,q} (x_{\,i} )\quad \left| \begin{array}{l}
 \;0 \le q \le n \\ 
 \;\forall i\;:\;0 \le i \le n \\ 
 \end{array} \right.\quad  \Rightarrow \quad p_{\,n} (x) = \sum\limits_{0 \le \,\,i\, \le \,n} {p_{\,q} (x_{\,i} )\frac{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {x - x_{\,j} } \right)} }}{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {x_{\,i}  - x_{\,j} } \right)} }}} \quad  = p_{\,q} (x)
$$
In particular
$$
x^{\,q} \quad \left| {\;0 \le q \le n\;} \right.\quad  = \sum\limits_{0 \le \,\,i\, \le \,n} {x_{\,i} ^{\,q} \frac{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {x - x_{\,j} } \right)} }}{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {x_{\,i}  - x_{\,j} } \right)} }}} 
$$
The algebric demonstration is not straightforward, it requires to expand the product in ${\left( {x - x_{\,j} } \right)}$,
recurring to Vieta's formulas and then collect the terms of the summation in $x^0$, $x^1$, 
and/or recurring to Divided Differences, …
But we can take a blick on what is going on, if we take the simple case of interpolating the points
$\left\{ {\left( {0,0} \right), \ldots ,\left( {k,k^{\,q} } \right), \ldots ,\left( {n,n^{\,q} } \right)} \right\}$
and limit our attention to the coefficient of $x^n$
$$
\begin{array}{l}
 \left[ {x^{\,n} } \right]p_{\,n} (x) = \sum\limits_{0 \le \,\,i\, \le \,n} {\frac{{i^{\,q} }}{{\prod\limits_{j\;:\;0 \le \,j\, \ne \,i\, \le \,n} {\left( {i - j} \right)} }}}  =  \\ 
  = \sum\limits_{0 \le \,\,i\, \le \,n} {\frac{{i^{\,q} }}{{\prod\limits_{0 \le \,j\,\, \le \,i - 1} {\left( {i - j} \right)} \prod\limits_{i + 1 \le \,j\,\, \le \,n} {\left( {i - j} \right)} }}}  =  \\ 
  = \sum\limits_{0 \le \,\,i\, \le \,n} {\frac{{i^{\,q} }}{{i!\prod\limits_{1 \le \,k\, \le \,n - i} {\left( { - k} \right)} }}}  = \sum\limits_{0 \le \,\,i\, \le \,n} {\left( { - 1} \right)^{\,n - i} \frac{{i^{\,q} }}{{i!\left( {n - i} \right)!}}}  =  \\ 
  = \frac{1}{{n!}}\sum\limits_{0 \le \,\,i\, \le \,n} {\left( { - 1} \right)^{\,n - i} \left( \begin{array}{c}
 n \\ 
 i \\ 
 \end{array} \right)i^{\,q}  = } \frac{1}{{n!}}\Delta _{\,x} ^n \,x^{\,q} \left| {_{x\, = \,0} } \right. =  \\ 
  = n{\rm th}\,{\rm coefficient}\,{\rm in}\,{\rm Newton}\,{\rm expansion}\,{\rm of}\,x^{\,q}  =  \\ 
  = \left\{ \begin{array}{l}
 0\;\;q < n \\ 
 1\;\;q = n \\ 
 \end{array} \right. \\ 
 \end{array}
$$
