Miklos Schweitzer 2014 Problem 8: polynomial inequality Look at problem 8 :

Let $n\geq 1$ be a fixed integer. Calculate the distance: 
  $$\inf_{p,f}\max_{x\in[0,1]}|f(x)-p(x)|$$ where $p$ runs over
  polynomials with degree less than $n$ with real coefficients and $f$
  runs over functions $$ f(x)=\sum_{k=n}^{+\infty}c_k\, x^k$$ defined on
  the closed interval $[0,1]$, where $c_k\geq 0$ and
  $\sum_{k=n}^{+\infty}c_k = 1.$

This is what I have so far.
Clearly for $n=1$, we have $1/2$.
I am conjecturing for $n>1$, we have $(n-1)^{(n-1)} / n^n$ or something similar to that? (just put $x^{(n-1)}$ and $x^n$ then use AM-GM). it's just weird that the pattern does not fit, so it's probably wrong. Any ideas?
 A: Your inequality does not hold since $x^{n-1}$ is not the best approximation polynomial of $x^n$ with respect to the uniform norm. By Chebyshev's theorem we have that if $p(x)$ is the best approximation polynomial for $f(x)$, then  $f(x)=p(x)$ holds for $\partial p+1$ points in $[0,1]$.
For instance, if $f(x)=x^n$ and $p(x)$ is the Lagrange interpolation polynomial with respect to the points $x=\frac{k}{n}$ for $k=1,2,\ldots,n$, since $f^{(n)}(x)=n!$ we have:
$$\|f(x)-p(x)\|_{\infty} = \left\|\prod_{k=1}^{n}\left(x-\frac{k}{n}\right)\right\|_{\infty}=\frac{n!}{n^n}$$
that is below your bound for any $n\geq 4$.
We can improve this bound by choosing our interpolation points more carefully: by selecting Chebyshev nodes, for instance: $x_k=\cos^2\frac{\pi(2k-1)}{4n}$ for $k=1,\ldots,n$.
In order to find the best approximation polynomial of $x^n$, have a look at the following answer of Noam Elkies on MO: https://mathoverflow.net/questions/70440/uniform-approximation-of-xn-by-a-degree-d-polynomial-estimating-the-error .
Since $\|T_n(2x-1)\|_\infty=1$, with the best choice for the interpolation nodes we have that the uniform error in approximating $x^n$ is always greater than $\color{red}{\frac{2}{4^n}}$.
Since for every function in our class we have $\frac{f^{(n)}(\xi)}{n!}\geq 1$ for any $\xi\in[0,1]$, $f(x)=x^n$ is the easiest function to approximate, and:
$$\inf_{p,f}\|f-p\|_{\infty}=\color{red}{\frac{2}{4^n}}.$$
A: Let $$t_n(x) = \frac1{2^{2n-1}} T_n(2x-1).$$
If $f-p=t_n$, i.e. $f(x)=x^n$ és $p(x) = x^n-t_n(x)$ then
$$\max_{0\le x\le 1} \big|f(x)-p(x)\big| = 
\max_{0\le x\le 1} \big|t_n(x)\big| = 
\frac1{2^{2n-1}} \max_{-1\le x\le 1} \big|T_n(x)\big| = 
\frac1{2^{2n-1}}.
$$
We show that this is the minimal possible value.
For all functions $f(x)$ and different reals $a_0,a_1,\ldots,a_n$, denote by
$f[a_0,a_1,\ldots,a_n]$ the divided difference of $f$ on the nodes $a_0,\ldots,a_n$. The divided difference of the power $X^N$ will be denoted by $X^N[a_0,a_1,\ldots,a_n]$. It is well-known (and can be proved by induction) that
$$
f[a_0,a_1,\ldots,a_n] = \sum_{j=0}^n \frac{f(a_j)}{\prod\limits_{k\ne
    j}(a_j-a_k)}, \tag1
$$
and
$$
X^N[a_0,a_1,\ldots,a_n] = \sum_{d_0+d_1+\dots+d_n=N-n}
a_0^{d_0}a_1^{d_1}\cdots a_n^{d_n}  \tag2
$$
where the exponents $d_0,\ldots,d_n$ run over the nonnegative integers. If
$N<n$ then the sum is empty.
Let $a_k=\frac12(1+\cos\frac{k\pi}n)$; then
$t_n(a_k)=\frac{(-1)^k}{2^{2n-1}}$. On the RHS of $(2)$ all summands are nonnegative; if $N\ge n$ then one of the terms is $a_0^{N-n}=1$. Hence,
\begin{align*}
  X^N[a_0,\ldots,a_n] &= 0   \quad \text{if $N<n$}; \\
  X^N[a_0,\ldots,a_n] &=1   \quad \text{if $N=n$}.   \\
  X^N[a_0,\ldots,a_n] &\ge 1 \quad \text{if $N>n$}.   \tag{3}
\end{align*}
Taking the divided difference term by term, we can see that
$$
t_n[a_0,\ldots,a_n] = X^n[a_0,\ldots,a_n] = 1.
$$
Now let $f(x) = \sum\limits_{k=n}^\infty c_k x^k$, and let
$p(x)=-\sum\limits_{k=0}^{n-1}c_kx^k$ be an arbitrary plynomial with degree less than $n$. Let $M=\max\limits_{[0,1]}|f-p|$ and consider the divided difference $(f-p)[a_0,\ldots,a_n]$.
From (1) we get
\begin{gather*}
  (f-p)[a_0,\ldots,a_n] = \sum_{j=0}^n
  \frac{f(a_j)-p(a_j)}{\prod\limits_{k\ne j}(a_j-a_k)} \le
  \sum_{j=0}^n \frac{M}{\Big|\prod\limits_{k\ne j}(a_j-a_k)\Big|} = \\
  = 2^{2n-1}M \sum_{j=0}^n \frac{(-1)^j/2^{2n-1}}{\prod\limits_{k\ne
      j}(a_j-a_k)} = 2^{2n-1}M \sum_{j=0}^n
  \frac{t_n(a_j)}{\prod\limits_{k\ne j}(a_j-a_k)} = \\ =
  2^{2n-1}M \cdot t_n[a_0,\ldots,a_n] = 2^{2n-1}M.
\end{gather*}
On the other hand, by (3),
$$
(f-p)[a_0,\ldots,a_n] = \sum_{k=0}^\infty c_k \cdot
X^k[a_0,\ldots,a_n] \ge \sum_{k=0}^{n-1} c_k \cdot 0 +
\sum_{k=n}^\infty c_k \cdot 1 = \sum_{k=n}^\infty c_k = 1. 
$$
Therefore,
$1 \le (f-p)[a_0,\ldots,a_n] \le 2^{2n-1}M$,
so
$M\ge\dfrac1{2^{2n-1}}$.
