Mathematical Reflections 2017, Issue 1 - Problem U402

Problem:
Let $n$ be a positive integer and let $P(x)$ be a polynomial of degree at most $n$ such that $|P(x)| \leq x+1$ for all $x \in [0,n]$. Prove that
$$|P(n+1)|+|P(-1)| \leq (n+2)(2^{n+1}-1)$$

Proposed by Alessandro Ventullo, Milan, Italy

Solution:
In order to prove the inequality, we deduce upper bounds for $|P(-1)|$ and $|P(n+1)|$.
Let $a_0,a_1,\ldots,a_n$ be $n+1$ distinct real numbers. Let $$L_i(x)=\prod_{\begin{smallmatrix} j=0\\ j\neq i\end{smallmatrix}}^{n} \dfrac{x-a_j}{a_i-a_j}$$ be the $n$-th degree Lagrange base polynomials for $i=0,1,\ldots,n$. We first prove that $\{L_0(x),\ldots,L_n(x)\}$ is a basis for $\mathbb{R}_n[x]$. Since $\dim \mathbb{R}_n[x]=n+1$, we only have to prove that $\{L_0(x),\ldots,L_n(x)\}$ are linearly independent. Let $(\lambda_0,\ldots,\lambda_{n+1}) \in \mathbb{R}^{n+1}$ such that $$\lambda_0L_0(x)+\ldots+\lambda_n L_n(x)=0$$ For each $i \in \{0,1,\ldots,n\}$, if $x=a_i$ we have $$0=\sum_{j=0}^n \lambda_j L_j(a_i)=\sum_{j=0}^n \lambda_j \delta_{ji}=\lambda_i,$$ so $\lambda_i=0$ for any $i \in \{0,1,\ldots,n\}$ and this shows that $\{L_0(x),\ldots,L_n(x)\}$ is a basis for $\mathbb{R}_n[x]$. So, if $P \in \mathbb{R}_n[x]$, there exists $(\lambda_0,\ldots,\lambda_n) \in \mathbb{R}^{n+1}$ such that $P(x)=\sum_{j=0}^n \lambda_jL_j(x)$. If $x=a_i$, then $$P(a_i)=\sum_{j=0}^n \lambda_j L_j(a_i)=\sum_{j=0}^n \lambda_j \delta_{ji}=\lambda_i,$$ so we can write $$P(x)=\sum_{j=0}^n P(a_j)L_j(x).$$ If $(a_0,a_1,\ldots,a_n)=(0,1,\ldots,n)$, we have $$P(x)=\sum_{j=0}^n P(j)L(x)$$
Now, we have $$\renewcommand{\arraystretch}{2} \begin{array}{lcl} \displaystyle |L_i(-1)|=\left| \prod_{\begin{smallmatrix} j=0\\ j\neq i\end{smallmatrix}}^{n} \dfrac{-1-j}{i-j} \right|&=& \displaystyle \prod_{j=0}^{i-1} \dfrac{j+1}{i-j} \prod_{j=i+1}^n \dfrac{j+1}{j-i}\\&=& \displaystyle \dfrac{i!}{i!}\cdot \dfrac{(n+1)!}{(i+1)!(n-i)!}\\&=& \displaystyle {n+1 \choose i+1} \end{array}$$
and
$$\renewcommand{\arraystretch}{2} \begin{array}{lcl} \displaystyle |L_i(n+1)|=\left| \prod_{\begin{smallmatrix} j=0\\ j\neq i\end{smallmatrix}}^{n} \dfrac{n+1-j}{i-j} \right|&=& \displaystyle \prod_{j=0}^{i-1} \dfrac{n+1-j}{i-j} \prod_{j=i+1}^n \dfrac{n+1-j}{j-i}\\&=& \displaystyle \dfrac{(n+1)!}{i!(n+1-i)!}\cdot \dfrac{(n-i)!}{(n-i)!}\\&=& \displaystyle {n+1 \choose i}. \end{array}$$
Hence, $$\renewcommand{\arraystretch}{2} \begin{array}{lcl} \displaystyle |P(-1)|=\left| \sum_{i=0}^n P(i)L_i(-1) \right| & \leq & \displaystyle \sum_{i=0}^n |P(i)L_i(-1)| \\ & \leq & \displaystyle \sum_{i=0}^n (i+1) {n+1 \choose i+1}\\&=& \displaystyle (n+1) \sum_{i=0}^n {n \choose i}\\&=&(n+1)2^n \end{array}$$ and
$$\renewcommand{\arraystretch}{2} \begin{array}{lcl} \displaystyle |P(n+1)|=\left| \sum_{i=0}^n P(i)L_i(n+1) \right| & \leq & \displaystyle \sum_{i=0}^n |P(i)L_i(n+1)| \\ & \leq & \displaystyle \sum_{i=0}^n (i+1) {n+1 \choose i} \\ &=& \displaystyle \sum_{i=0}^n i{n+1 \choose i}+\sum_{i=0}^n {n+1 \choose i} \\ &=& \displaystyle (n+1) \sum_{i=1}^n {n \choose i-1}+ \sum_{i=0}^n {n+1 \choose i} \\&=&(n+1)(2^n-1)+(2^{n+1}-1). \end{array}$$
Adding the last two inequalities, we get the desired inequality.