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.

  • $\begingroup$ Have you tried induction on $n$? $\endgroup$ – 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}.$$

So the leading coefficient is

$$\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$).

  • $\begingroup$ I tried to prove that last quantity is exactly 1, but don't know how? $\endgroup$ – silent_rain Aug 16 '15 at 23:49
  • $\begingroup$ @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$. $\endgroup$ – Ian Aug 16 '15 at 23:52
  • $\begingroup$ Ok, thanks a lot... So, now it is proved for case $x_i = i +s$, how can I generalize it? $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.