Prove that from $(n+1)$ given points a unique polynomial of $n$ degree will pass. Also find its general expression. In the above question we have to prove that any polynomial say $f(x)$ with $n^\text{th}$ degree may pass through $n+1$ points along with its uniqueness and existence. I tried this question with contradiction but couldn’t reach anything conclusive. Anyone of the bright mathematicians may help in this. I would be grateful.
 A: Notation: Let $x_0, \ldots, x_n$ be the $n+1$ (distinct) points at which the function's values are given.  

Existence 
For $i = 0, \ldots, n$, define 
$$P_i(x) = \prod_{j = 0, j\neq i}^n \dfrac{x - x_j}{x_i - x_j}.$$
Then, $P_i$ has the following properties (for all $i = 0, \ldots, n$):  


*

*$\deg P_i = n$  

*$P_i(x_i) = 1$

*$P_i(x_j) = 0$ for all $j \neq i$, $0 \le j \le n$
Now, define $P(x)$ as
$$P(x) = \sum_{j=0}^n f(x_j)P_j(x).$$
Note the following properties about $P(x)$:


*

*$\deg P \le n$. (This is because $P(x)$ is a sum of polynomials, each having degree $n$ and the degree cannot increase.)  

*$P(x_i) = f(x_i)$ for all $0 \le i \le n$.
To see this, simply substitute $x = x_i$ in the definition of $P(x)$ and note that $P_i(x_i) = 1$ and $P_j(x_i) = 0$ for $j \neq i$.


Thus, $P(x)$ is one such desired polynomial.

Uniqueness
For this, we use the following lemma:  
Lemma. Let $p(x) = a_nx^n + \cdots + a_1x + a_0$ be such $p(x_i) = 0$ for $0 \le i \le n$. Then, $a_i = 0$ for all $0 \le i \le n$.
(Note that all the $x_i$s are distinct.)
Proof. Since $p(x_i) = 0$, we see that $x - x_i$ is a root of $p(x)$. Thus, we may write
$$p(x) = K(x - x_0)\cdots(x - x_n).$$
If $K \neq 0$, then the RHS has degree $n+1$ while the LHS has degree $n$, a contradiction. Thus, $K = 0$ and the result follows.
Now, we prove the uniqueness of $P(x)$ obtained earlier. Let $Q(x)$ be any polynomial of degree $\le n$ such that $Q(x_i) = f(x_i)$ for all $0 \le i \le n$.
Then, define 
$$p(x) = P(x) - Q(x).$$
We have that $\deg p(x) \le n$ and $p(x_i) = 0$ for all $0 \le i \le n$. By the previous lemma, we have that $p(x) = 0$ and thus, $P(x) = Q(x)$, as desired.
A: When presented purely formally, Lagrange Interpolation can seem overly complicated. But you can break it down yourself.
Let's suppose that $(x_0, y_0), (x_1, y_1), \ldots, (x_n, y_n)$ are the $n+1$ points that you want to interpolate. In this set-up $x_0, x_1, \ldots x_n$ are all distinct numbers.
One approach you might try is to combine several polynomials into a sum that has the properties that you want. It's easy to build a polynomial $p_0$ such that $p(x_0)=y_0$ and $p_0(x_i)=0$ for all other $i$. Here's the formula:
$$p_0(x)=(x-x_1)(x-x_2)\cdots(x-x_n)\cdot\frac{y_0}{(x_0-x_1)(x_0-x_2)\cdots(x_0-x_n)}$$
Now you do something similar for $p_1, p_2, \ldots, p_n$ and the polynomial $p_0+p_1+\cdots+p_n$ will work.
