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