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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s