If the points $x_1,x_2,\ldots,x_n$ are distinct,then... I am stuck on the following problem that says:  

If the points $x_1,x_2,\ldots,x_n$ are distinct,then for arbitrary real values $y_1,y_2,\ldots,y_n$, prove that the degree of the unique interpolating polynomial $p(x)$ such that $p(x_i)=y_i,\,\,(1 \le i \le n)$ is $\le n-1$. 

I think I have to use Lagrange polynomial but I could not put the things together . Can someone help? Thanks in advance for your time.
 A: As currently worded, the assertion is false. There are infinitely many interpolating polynomials, of arbitrarily high degrees. For if $P(x)$ is an interpolating polynomial, so is 
$$P(x)+Q(x)(x-x_1)(x-x_2)\cdots(x-x_n)$$
for any polynomial $Q(x)$.
What we can say is that there is a unique interpolating polynomial of degree $\le n-1$.
To prove that, we need to do two things (i) show that there is an interpolating polynomial of degree $\le n-1$ and (ii) show that there is at most one.
For (i) use the ordinary Lagrange polynomial.
For (ii), suppose that $P$ and $Q$ are interpolating polynomials of degree $\le n-1$, Then $P-Q$ is $0$ at $x_1,x_2 ,\dots,x_n$. But a polynomial of degree $\le n-1$ can have $n$ or more distinct roots only if it is the identically $0$ polynomial. It follows that $P-Q$ is identically $0$. 
A: I like to think it little bit differently. Such a polynomial exists uniquely if you try to see it as follows.
Take $y_i = f(x_i)$ for $ i = 1, 2, \dots, n$. $f$ is a function whose analytical formula is unknown.
Take interpolation polynomial $L_{n-1}(x)$ of degree $n-1$ s.t. $L_n(x_i) = f(x_i)$ for $i= 1, 2,\dots,n$.
Write $L_{n-1}(x) = a_0 + a_1 x + \dots + a_{n-1} x^{n-1}$
Thus $a_0 + a_1x_i + \dots + a_{n-1}x_i^{n-1} = f(x_i)$
Put different values of $i = 1, 2, \dots,n$ and put $f(x_i) = y_i$ which are known.
You shall get $(n)$ linear equation with $(n)$ unknowns $a_0, a_1, \dots, a_{n-1}$.
The determinant of the corresponding matrix is Vandermonde's determinant with non zero value.
So the values of coefficients can be determined uniquely i.e. the interpolation polynomial will find out uniquely
