Numerical mathematics, Lagrange interpolation..

I am trying to solve this problem, but I don't have any idea. Maybe it doesn't look at first sight that Lagrange interpolation can be used, but I found this problem in that chapter of Numerical methods, so I suppose that interpolation can be used.

The problem is:

Let $x_0,x_1,...,x_n$ be random integer numbers so that is $x_0<x_1<...<x_n$. Prove that for each polynomial $P(x)=x^n+a_1x^{n−1}+...+a_n$ is $max_{0≤i≤n}|P(x_i)|≥\frac{n!}{2^n}$.

Does anyone have idea? Thanks in advance.

• Have you tried induction on $n$? – Gerry Myerson Jul 13 '15 at 13:10

Let $y_0,\dots,y_n$ be such that $|y_i|<\frac{n!}{2^n}$ for all $i$. Let us prove that the interpolating polynomial for $(x_i,y_i)$ cannot have a leading coefficient of $1$. I'll work with the case $x_i=i+s$ for a fixed integer $s$ and leave it to you to generalize. We write the interpolating polynomial in Lagrange form:

$$P(x)=\sum_{i=0}^n y_i \prod_{j=0,j \neq i}^n \frac{x-x_j}{x_i-x_j}.$$

$$\sum_{i=0}^n y_i \prod_{j=0,j \neq i} \frac{1}{x_i - x_j}.$$

So by the triangle inequality, the assumption on the $y_i$, and my choice of the $x_i$, the absolute value of the leading coefficient is strictly less than

$$\frac{n!}{2^n} \sum_{i=0}^n \prod_{j=0,j \neq i}^n \frac{1}{|i-j|}.$$

This quantity is exactly $1$, so the absolute value of the leading coefficient is strictly less than $1$. I'll leave it to you to prove this. It may help to expand out the product for a small value of $n$ and $i$ (something like $n=5,i=2$).

• I tried to prove that last quantity is exactly 1, but don't know how? – silent_rain Aug 16 '15 at 23:49
• @silent_rain Rewriting it as $\frac{1}{2^n} \sum_{i=0}^n \prod_{j=0,j \neq i}^n \frac{n!}{|i-j|}$, the binomial theorem winds up telling you that this is $\frac{(1+1)^n}{2^n}=1$. – Ian Aug 16 '15 at 23:52
• Ok, thanks a lot... So, now it is proved for case $x_i = i +s$, how can I generalize it? – silent_rain Aug 17 '15 at 0:01

You should read the following: http://math.jasonbhill.com/courses/fall-2010-math-2300-005/lectures/taylor-polynomial-error-bounds