Largest absolute value of a polynomial of degree $n$ on $\{0,1,\ldots,n\}$ Consider a polynomial $P_n(x)\in\mathbb{R}[x]$, of degree $n\geq1$, of the form
$$P_n(x)=c_0+c_1x+c_2x^2+\cdots+c_{n-1}x^{n-1}+x^n.$$
To illustrate the question, take $P_1(x)=c_0+x$ so that $P_1(0)=c_0$ and  $P_1(1)=c_0+1$. If $\vert c_0\vert<\frac12$ then $\vert c_0+1\vert\geq1-\vert c_0\vert>1-\frac12=\frac12$. That means, $\pmb{\max}\{\vert P_1(0)\vert,\vert P_1(1)\vert\}\geq\frac12$.
In general,

QUESTION. is this true?
  $$\pmb{\max}\{\vert P_n(0)\vert,\vert P_n(1)\vert,\vert P_n(2)\vert,\dots,\vert P_n(n)\vert\}\geq\frac{n!}{2^n}.$$

 A: You can write your polynomial as
$$ P(x) = \sum_{k = 0}^n P(k) L_{n,k}(x) ,$$
where $L_{n,k}$ are the Lagrange interpolation polynomials with nodes at $0, 1, \ldots, n$. Note that $(-1)^{n - k} L_{n,k}$ has positive coefficient at $x^n$. Thus, with the constraint $$\max\{|P(k)| : k = 0, 1, \ldots, n\} \leqslant 1,$$ the largest possible value of the coefficient of $P$ at $x^n$ is attained by
$$ \bar P(x) = \sum_{k = 0}^n (-1)^{n - k} L_{n,k}(x) , $$
and the coefficient of $\bar P$ at $x^n$ is equal to
$$ \sum_{k = 0}^n \prod_{\substack{0 \leqslant j \leqslant n \\ j \ne k}} \frac{1}{|k - j|} \, .$$
In other words, if the coefficient at $x^n$ is to be equal to $1$, the least possible value of $\max\{|P(k)| : k = 0, 1, \ldots, n\}$ is
$$ \biggl(\sum_{k = 0}^n \prod_{\substack{0 \leqslant j \leqslant n \\ j \ne k}} \frac{1}{|k - j|} \biggr)^{-1} .$$
It remains to note that
$$ \sum_{k = 0}^n \prod_{\substack{0 \leqslant j \leqslant n \\ j \ne k}} \frac{1}{|k - j|} = \sum_{k = 0}^n \frac{1}{k! (n - k)!} = \frac{1}{n!} \sum_{k = 0}^n \binom{n}{k} = \frac{2^n}{n!} \, .$$
A: Lagrange interpolation suggested by Mateusz Kwaśnicki is perfectly ok, but in this case it is probably easier to use the finite difference formula $$\sum_{i=0}^{n} (-1)^{i}{n\choose i}P(t+n-i)=\Delta^n P=n!$$
for $t=0$, where $\Delta:f(t)\to f(t+1)-f(t)$ is a finite difference operator.
Also this very statement is well known, in case if you need references.
