Confused with an interpolation problem using Lagrange. I'm really confused about the following interpolating problem.Not sure if this is the right method.
For $n =3$, explain why
$$ x_0^jL_o(x) + x_1^jL_1(x) + x_2^jL_2(x) + x_3^jL_3(x) = x^j, \ \ j \leq 3$$
Let $Q_3(x)=x_0^jL_o(x) + x_1^jL_1(x) + x_2^jL_2(x) + x_3^jL_3(x)$. Notice that: $$L_i(x_j) = \delta_{ij}$$
Now, define $R(x) = Q_3(x)-x^j$. First, since $\deg(Q_3) \leq 3$ and $j \leq 3$, then $\deg(R) \leq 3$.Now:
$$R(x_i) = 0 \ \text{for } i= 0,1,2,3$$
therefore it has $4$ roots, but has degree $3$ and this cannot happen unless $R_3(x) \equiv 0 \Rightarrow Q_3(x) = x^j$.
 A: A few things to note:


*

*By defining 
$$\tilde L_j(x) = \prod_{i\neq j} (x - x_i)$$
We obtain a polynomial of degree $n$ (since $i$ ranges over $0, 1,\ldots, j-1, j+1,\ldots, n$), which has zeros at each point $x_i$ for $i \neq j$. 

*Normalizing/scaling the polynomial gives the Lagrange polynomial 
$$ L_j(x) = \prod_{i\neq j} \frac{x-x_i}{x_j-x_i}$$
which, basically, allows for $L_j(x_i) = \delta_{ij}$. 

*The motivation for describing a function like this is the following. Suppose that some function $f : \mathbb R \to \mathbb R$ is responsible for the data generation process - i.e. $f(x_j) = y_j$, resulting in a sequence of pairs $(x_j, y_j), j =0,\ldots, n$. Note that I have deviated from the notation you used above to allow $f$ to be a more general function. Then $y_j L_j(x_i) = 0$ if $i \neq j$, and $y_j L_j(x_i) = y_j$ if $i = j$. In particular, if we take a linear combination of $(L_j(x))_{j=0}^n$, then these functions do not "interfere" with each other at the interpolation points $(x_j)_{j=0}^n$. 

*Now define the remainder function $R(x)$ by 
$$ R(x) = Q_j(x) - f(x)$$
In the sequence of steps you showed above, you assumed that $f$ is a polynomial of degree no greater than $k$ - i.e. $f(x) = x^k$, where $k\leq 3$. So by the argument you gave above, it follows that $R \equiv 0$ so that $Q_j(x) = f(x)$ (since a polynomial can have no more roots than its degree).
