# Lagrange’s interpolation polynomial

In this article, I will use Lagrange polynomial to solve some polynomial problems from Mathematical Olympiads.

1) Lagrange’s interpolation polynomial
Theorem. Let $n$ be a positive integer and $x_0,x_1,\cdots,x_{n};y_0,y_1,\cdots,y_n$ are complex numbers such that $x_i\not=x_j$ if $i\not=j$. Then there exists precisely one polynomial $P(x)$ of degree not greater than $n$ such that $P(x_i)=y_i\,\,\forall i=\overline{0,n}$.
Proof. If $P$ and $Q$ are polynomials of degree not greater than $n$ such that $P(x_i)=Q(x_i)=y_i\,\,\forall i=\overline{0,n}$ then the polynomial $P-Q$ of degree not greater than $n$ and has at least $n+1$ distinct roots, therefore $P-Q$ is the zero polynomial and hence $P=Q$.

Now if $\displaystyle P(x)=\sum_{i=0}^ny_i\prod_{j\not =i}\frac{x-x_j}{x_i-x_j}$ then $P(x)$ is a polynomial of degree not greater than $n$ and $P(x_i)=y_i\,\,\forall i=\overline{0,n}$. $\Box$

The polynomial $\displaystyle\sum_{i=0}^ny_i\prod_{j\not =i}\frac{x-x_j}{x_i-x_j}$ is called Lagrange’s interpolation polynomial or Lagrange’s polynomial at nodes $x_0,x_1,\cdots,x_{n}$.

Corollary. If $P(x)$ is a polynomial of degree not greater than $n\,\, (n\in\mathbb{Z},n>0)$ and $x_0,x_1,\cdots,x_{n}$ are complex numbers such that $x_i\not=x_j$ if $i\not=j$ then $\displaystyle P(x)=\sum_{i=0}^nP(x_i)\prod_{j\not =i}\frac{x-x_j}{x_i-x_j}$.
2) Examples
Example 1. Let $A(x)=x^{81}+x^{49}+x^{25}+x^9+x$ and $B(x)=x^3-x$ be polynomials. Find the remainder in the division of $A(x)$ by $B(x)$.
Solution 1. Asume $Q(x)$ and $R(x)$ are the quotient and remainder in the division of $A(x)$ by $B(x)$, respectively. We have
$A(x)=B(x)Q(x)+R(x),\,\,\,\text{and}\,\, \deg R<3.\,\,\, (1)$
Because $B(0)=B(1)=B(-1)=0$ and $(1)$ we have $R(0)=0,R(1)=5$ and $R(-1)=-5$, therefore use Lagrange’s interpolation polynomial at nodes $0;1$ and $-1$ we have
$\displaystyle R(x)=R(0).\frac{(x-1)(x+1)}{(0-1)(0+1)}+R(1).\frac{(x-0)(x+1)}{(1-0)(1+1)}+R(-1).\frac{(x-0)(x-1)}{(-1-0)(-1-1)}$
$=\frac{5}{2}x(x+1)-\frac{5}{2}x(x-1)=5x.$
Solution 2. We have $x^3\equiv x\pmod{B(x)}$ and therefore
$A(x)=(x^3)^{27}+(x^3)^{16}x+(x^3)^8x+(x^3)^3+x\equiv x^{27}+x^{17}+x^9+x^3+x$
$=(x^3)^9+(x^3)^5x^2+(x^3)^3+x^3+x\equiv x^9+x^7+2x^3+x$
$=(x^3)^3+(x^3)^2x+2x^3+x\equiv 4x^3+x\equiv 5x\pmod{B(x)}.$
Because $\deg (5x)=1<\deg B(x)$, we have $5x$ is the remainder in the division of $A(x)$ by $B(x)$.
Example 2. Let $P$ be a polynomial of degree $n\,\,(n\in\mathbb{Z},n>0)$ satisfying $\displaystyle P(k)=\frac{k}{k+1}\,\,\forall k=\overline{0,n}.$ Determine $P(n+1)$.
Solution 1. Use Lagrange’s interpolation polynomial at nodes $0,1,\cdots,n$ we have
$\displaystyle P(x)=\sum_{k=0}^nP(k)\prod_{j\not =k}\frac{x-j}{k-j}=\sum_{k=0}^n\frac{k}{k+1}\prod_{j\not =k}\frac{x-j}{k-j}=\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}\prod_{j\not =k}(x-j).$
Therefore
$\displaystyle P(n+1)=\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}\prod_{j\not =k}(n+1-j)=\sum_{k=0}^n\frac{(-1)^{n-k}k}{(k+1)!(n-k)!}.\frac{(n+1)!}{n+1-k}$
$\displaystyle =\frac{1}{n+2}\sum_{k=0}^nk(-1)^{n-k}C^{k+1}_{n+2}=\frac{1}{n+2}\sum_{k=0}^n\left[(k+1)(-1)^{n-k}C_{n+2}^{k+1}+(-1)^{n-k+1}C_{n+2}^{k+1}\right]$
$\displaystyle =\frac{1}{n+2}\left(\sum_{k=0}^n(-1)^{n-k}(n+2)C_{n+1}^k+\sum_{i=1}^{n+1}(-1)^{n+2-i}C_{n+2}^i\right)=\dfrac{n+1+(-1)^{n+1}}{n+2}.$
Solution 2. We have the polynomial $Q(x)=(x+1)P(x)-x$ of degree $n+1$ and $0, 1, 2,\cdots, n$ are its roots, therefore
$Q(x)=Cx(x-1)(x-2)\cdots (x-n),$ for some constant $C$.
Because $Q(-1)=1$, we have
$C(-1)(-2)(-3)\cdots (-n-1)=(-1)^{n+1}(n+1)!C=1,$
therefore $\displaystyle C=\dfrac{(-1)^{n+1}}{(n+1)!}$ and
$\displaystyle Q(x)=\frac{(-1)^{n+1}}{(n+1)!}x(x-1)(x-2)\cdots (x-n).$
Hence $Q(n+1)=\dfrac{(-1)^{n+1}}{(n+1)!}(n+1)!=(-1)^{n+1}$.
Note that $P(n+1)=\dfrac{Q(n+1)+n+1}{n+2}=\dfrac{(-1)^{n+1}+n+1}{n+2}$.
Therefore $P(n+1)$ is equal to $1$ if $n$ is odd and equal to $\dfrac{n}{n+2}$ if $n$ is even.
Example 3. Let $n$ be a positive integer. Suppose $x_0, x_1, \ldots , x_n$ are integers and $x_0 > x_1 > \cdots > x_n.$ Prove that at least one of the numbers $|F(x_0)|, |F(x_1)|, |F(x_2)|, \ldots, |F(x_n)|,$ where $F(x) = x^n + a_1x^{n-1} + \cdots+ a_n\,\, (\quad a_i \in \mathbb R, \quad i = 1, \ldots , n)$ is greater than or equal to $\dfrac{n!}{2^n}.$
Solution. Assume that $|F(x_i)|<\dfrac{n!}{2^n}\,\,\forall i=\overline{0,n}$. Use Lagrange’s interpolation polynomial at nodes $x_0,x_1,\cdots,x_n$ we have
$\displaystyle x^n + a_1x^{n-1} + \cdots+ a_n=\sum_{k=0}^nF(x_k)\prod_{j\not =k}\frac{x-x_j}{x_k-x_j},$
see the coefficient of $x^n$ we have
$\displaystyle 1=\left|\sum_{k=0}^n\prod_{j\not =k}\frac{F(x_k)}{x_k-x_j}\right|\leq \sum_{k=0}^n\prod_{j\not =k}\frac{|F(x_k)|}{|x_k-x_j|}<\sum_{k=0}^n\prod_{j\not =k}\frac{\frac{n!}{2^n}}{|x_k-x_j|}$
$\displaystyle\leq \sum_{k=0}^n\prod_{j\not =k}\frac{\frac{n!}{2^n}}{|k-j|}=\frac{1}{2^n}\sum_{k=0}^nC_n^k=1,\quad \text{a contradiction},$
and therefore at least one of the numbers $|F(x_0)|, |F(x_1)|, |F(x_2)|, \ldots, |F(x_n)|$ is greater than or equal to $\dfrac{n!}{2^n}.$
Example 4. $P(x)$ is a polynomial of degree $2n\,\, (n\in\mathbb{N})$ such that
$P(0) = P(2) = \cdots = P(2n) = 0,\,\,\, P(1) = P(3) = \cdots = P(2n-1) = 2,$
and $P(2n+1) =-30.$ Determine $n$.
Solution. Use Lagrange’s interpolation polynomial at nodes $0,1,2\cdots,2n$ we have
$\displaystyle P(x)-1=\sum_{k=0}^{2n}(P(k)-1)\prod_{j\not =k}\frac{x-j}{k-j}=\sum_{k=0}^{2n}(-1)^{k+1}\prod_{j\not =k}\frac{x-j}{k-j},$
and therefore $\displaystyle P(2n+1)-1=-\sum_{k=0}^{2n}C^k_{2n+1}=1-2^{2n+1}$, but by hypothesis $P(2n+1)=-30$, hence we have $-31=1-2^{2n+1}$, so $n=2$.

Example 5. Prove that for any real number $a$ we have the following identity
$\sum_{k = 0}^n( - 1)^kC_n^k(a - k)^n = n!\, \forall n\in\mathbb{N}.$
Solution. Assume that $a = 0$ and $n\geq 3$, then we need to prove
$\sum_{k = 0}^n( - 1)^{n + k}C_n^k( k)^n = n!\, (*).$
By Lagrange’s Interpolation polynomial at nodes $1,2,\cdots,n$ we have
$\displaystyle x^n - (x - 1)(x - 2)\cdots (x - n) = \sum_{k = 1}^nk^n\cdot\prod_{i\not = k}\dfrac{x - i}{k - i}\, (**).$
Now, in $(**)$, setting $x = 0$ we have
$( - 1)^{n + 1}\cdot n! = \sum_{k = 1}^nk^n\cdot \dfrac{1}{k}\cdot \dfrac{( - 1)^{n - 1}\cdot n!}{(k - 1)!\cdot (n - k)!\cdot ( - 1)^{n - k}},$
and we are done.

Example 6. Let $x,y,z$ and $t$ be real numbers satisfying
$\displaystyle\begin{cases} \frac{x^2}{2^2-1^2}+\frac{y^2}{2^2-3^2}+\frac{z^2}{2^2-5^2}+\frac{t^2}{2^2-7^2}=1 \\ \frac{x^2}{4^2-1^2}+\frac{y^2}{4^2-3^2}+\frac{z^2}{4^2-5^2}+\frac{t^2}{4^2-7^2}=1 \\ \frac{x^2}{6^2-1^2}+\frac{y^2}{6^2-3^2}+\frac{z^2}{6^2-5^2}+\frac{t^2}{6^2-7^2}=1 \\ \frac{x^2}{8^2-1^2}+\frac{y^2}{8^2-3^2}+\frac{z^2}{8^2-5^2}+\frac{t^2}{8^2-7^2}=1. \end{cases}$
Determine $x^2+y^2+z^2+t^2$.
Solution 1. Setting $l_i=(2i-1)^2,c_i=(2i)^2\,\,\forall i=\overline{1,4}$ and
$f(x)=\prod_{i=1}^4(x-l_i)-\prod_{i=1}^4(x-c_i).$
We have $\deg f\leq 3$, and therefore by Lagrange’s Interpolation polynomial at nodes $l_1,l_2,l_3,l_4$ we obtain
$\displaystyle f(x)=\sum_{i=1}^4f(l_i)\prod_{j\not =i}\frac{x-l_j}{l_i-l_j}.\,\,\, (1)$
From $(1)$ and $\displaystyle f(c_j)=\prod_{i=1}^4(c_j-l_i)\,\,\forall j=\overline{1,4}$ we have
$\displaystyle\prod_{i=1}^4(c_j-l_i)=\sum_{i=1}^4f(l_i)\prod_{k\not =i}\frac{c_j-l_k}{l_i-l_k}\,\,\forall j=\overline{1,4},$ and hence
$\displaystyle\frac{\alpha_1}{c_j-l_1}+\frac{\alpha_2}{c_j-l_2}+\frac{\alpha_3}{c_j-l_3}+\frac{\alpha_4}{c_j-l_4}=1\,\,\forall j=\overline{1,4},$
where $\displaystyle\alpha_i=\frac{f(l_i)}{\prod_{j\not=i}(l_i-l_j)}\,\,\forall i=\overline{1,4}.$
See coeficients of $x^3$ in both sides of $(1)$ we have $\displaystyle\sum_{i=1}^4\alpha_i=\sum_{i=1}^4(c_i-l_i)=36,$ and therefore $\displaystyle x^2+y^2+z^2+t^2=\sum_{i=1}^4\alpha_i=36.$

Solution 2. From hypothesis we have
$\displaystyle\frac{x^2}{w-1^2}+\frac{y^2}{w-3^2}+\frac{z^2}{w-5^2}+\frac{t^2}{w-7^2}=1\,\,\forall w\in \{4,16,36,64\},$ and therefore $4,16,36$ and $64$ are roots of the polynomial
$P(w)=\prod_{i=1}^4(w-(2i-1)^2)-x^2(w-3^2)(w-5^2)(w-7^2)-\cdots$
$= w^4-(x^2+y^2+z^2+t^2+1^2+3^2+5^2+7^2)w^3+\cdots$
hence $P(w)=(w-4)(w-16)(w-36)(w-64)$. By see coeficients of $w^3$ we have
$-(x^2+y^2+z^2+t^2+1^2+3^2+5^2+7^2)=-(4+16+36+64),$
so $x^2+y^2+z^2+t^2=36.$

Example 7. Let $ABC$ be a triangle with $BC=a,CA=b$ and $AB=c$. Prove that for any points $P,Q$ in the plane $(ABC)$ we have
$a.PA.QA+b.PB.QB+c.PC.QC\geq abc.$
Solution. In the complex plane $(ABC)$ we assume that
$A=x_1,B=x_2,C=x_3,P=p,Q=q.$
By Lagrange’s Interpolation polynomial at nodes $x_1,x_2,x_3$ we have
$\displaystyle (x-p)(x-q)=\sum_{i=1}^3(x_i-p)(x_i-q)\prod_{j\not=i}\frac{x-x_j}{x_i-x_j},$
see coeficients of $x^2$ in the both sides we obtain
$\displaystyle\frac{(x_1-p)(x_1-q)}{(x_1-x_2)(x_1-x_3)}+\frac{(x_2-p)(x_2-q)}{(x_2-x_3)(x_2-x_1)}+\frac{(x_3-p)(x_3-q)}{(x_3-x_1)(x_3-x_2)}=1,$
and therefore
$\displaystyle 1\leq \frac{|x_1-p|.|x_1-q|}{|x_1-x_2|.|x_1-x_3|}+\frac{|x_2-p|.|x_2-q|}{|x_2-x_3|.|x_2-x_1|}+\frac{|x_3-p|.|x_3-q|}{|x_3-x_1|.|x_3-x_2|},$
but $|x_2-x_1|=AB,\cdots$ and $|x_1-p|=AP,\cdots$, therefore
$\displaystyle 1\leq \frac{PA.QA}{AB.AC}+\frac{PB.QB}{BC.BA}+\frac{PC.QC}{CA.CB},$
and we are done.
Example 8. Find all polynomials $P(x)$ with real coefficients such that for every positive integer $n$ there exists a rational $r$ with $P(r)=n$.
Solution on AoPS. Assume that $P(x)\in\mathbb{R}[x]$ is a polynomial satisfying for every positive integer $n$ there exists a rational $r$ with $P(r)=n$.
Clearly $P(x)$ can’t be constant, so $d:= \deg P\ge 1$. For all $n\in\mathbb{N}$ take $n\in\mathbb{Q}$ such that $P(r_n) = n$. $P(r_1) = 1,P(r_2) = 2,\ldots,P(r_{d + 1}) = d + 1$ gives $P(x)\in\mathbb{Q}[x]$ using the Lagrange’s interpolation polynomial at nodes $r_1,r_2,\cdots,r_{d+1}$.
Then for some $t\in\mathbb{N}$ we have $tP(x)\in\mathbb{Z}[x]$ with leading coefficient $m\in\mathbb{Z}\setminus\{0\}$. But then $tP(x) - tn\in\mathbb{Z}[x]$ has rational root $r_n$ and also leading coefficient $m$. So the denominator of $r_n$ divides $m$, i.e. $\displaystyle r_n\in \frac{1}{m}\mathbb{Z}$ for all $n\in\mathbb{N}$.
Now assume $d = \deg P \geq 2$. Then $\displaystyle\left |\frac{P(x)}{x}\right |\to +\infty$ for $|x|\to +\infty$, and we find $N\in\mathbb{N}$ large enough with $\displaystyle\left |\frac{P(x)}{x}\right | > 2|m|$ for all $|x|\ge N$.
But $\displaystyle\frac{1}{m}\mathbb{Z}\cap ( - N,N)$ contains exactly $2|m|N - 1$ elements. So among the $2|m|N$ different numbers $\displaystyle r_1,r_2,\ldots,r_{2|m|N}\in\frac{1}{m}\mathbb{Z}$
we must find $|r_k|\ge N$ for some $k = 1,\ldots ,2|m|N$. This gives $\displaystyle 2|m| < \left |\frac{P(r_k)}{r_k}\right | = \frac{k}{|r_k|}\le {2|m|N\over N} = 2|m|$, a contradiction.
So we must have $P(x)\in\mathbb{Q}[x]$ with $\deg P = 1$, which is indeed a solution for the problem.

## 3 thoughts on “Lagrange’s interpolation polynomial”

1. From Wiki: In numerical analysis, Lagrange polynomials are used for polynomial interpolation. For a given set of distinct points $x_j$ and numbers $y_j,$ the Lagrange polynomial is the polynomial of the least degree that at each point $x_j$ assumes the corresponding value $y_j$ (i.e. the functions coincide at each point). The interpolating polynomial of the least degree is unique, however, and it is therefore more appropriate to speak of “the Lagrange form” of that unique polynomial rather than “the Lagrange interpolation polynomial”, since the same polynomial can be arrived at through multiple methods. Although named after Joseph Louis Lagrange, who published it in 1795, it was first discovered in 1779 by Edward Waring and it is also an easy consequence of a formula published in 1783 by Leonhard Euler.