This is an exercise I liked to solve and I wanted to share it.
Find the minimum of $\displaystyle\sum_{i=0}^n(i^n-P(i))^2$ with $P$ in $\mathbb{R}_{n-1}[X]$
Where $\mathbb{R}_{p}[X]$ denotes the ring of real polynomials whose degree is at most $p$
Do not hesitate to comment and share your thoughts. Feel free to correct me (especially my English).
First of all, I thought of using the inner product on $\mathbb{R}_{n}[X]$ defined by:
$$\langle P|Q\rangle = \sum_{i=0}^nP(i)Q(i)$$
Proof it is an inner product:
$\bullet$ $\mathbb{R}_{n}[X]$ is a real vector space and $\langle \cdot | \cdot \rangle$ is well defined.
$\bullet$ $\forall (P,Q) \in(\mathbb{R}_{n}[X])^2, \, \displaystyle \langle P|Q\rangle = \sum_{i=0}^nP(i)Q(i) = \sum_{i=0}^nQ(i)P(i) = \langle Q|P\rangle $ so $\langle \cdot | \cdot \rangle$ is symmetric.
$\bullet \, \forall (P,Q,R) \in(\mathbb{R}_{n}[X])^3, \forall\lambda \in \mathbb{R},$
$$ \langle P+\lambda Q |R\rangle = \displaystyle \sum_{i=0}^n (P+\lambda Q)(i) R(i)=\sum_{i=0}^nP(i)R(i)+\lambda\sum_{i=0}^nQ(i)R(i) = \langle P|R\rangle+\lambda \langle Q|R\rangle$$
Hence $\langle \cdot | \cdot \rangle$ is linear on the left, but as it is symmetric, it is also linear on the right. Therefore $\langle \cdot | \cdot \rangle$ is bilinear.
$\bullet$ For all $P \in \mathbb{R}_{n}[X]$, we have, $$\langle P | P \rangle = \sum_{i=0}^n P(i)^2\geq0$$
Moreover, if $\langle P | P \rangle =0$ then for all $i \in \{0,\dots,n\}, P(i) = 0$, therefore $P$ has at least $n+1$ roots and its degree is at most $n$, hence $P=0$. This proves the positive definiteness.
Consequently, as $\langle \cdot|\cdot\rangle$ is an inner product let $\lVert \cdot \rVert$ denote its related norm. We have by the theorem of the orthogonal projection,
$$\min_{P \in \mathbb{R}_{n-1}[X]} \left( \displaystyle\sum_{i=0}^n(i^n-P(i))^2 \right) = \min_{P \in \mathbb{R}_{n-1}[X]} \lVert X^n -P \rVert^2 = \left(\min_{P \in \mathbb{R}_{n-1}[X]} \lVert X^n -P \rVert\right)^2 = \lVert X^n -p(X^n)\rVert^2$$
Where $p(X^n)$ is the orthogonal projection of $X^n$ on $\mathbb{R}_{n-1}[X]$.
Let $Q = X^n-p(X^n)$. As $p(X^n) \in \mathbb{R}_{n-1}[X]$ one can see that $Q$ is a monic polynomial and $n$ is its degree.
For all $1\leq\ell\leq n$, let $Q_{\ell} = \displaystyle \prod_{\substack{i=1\\i \neq \ell}}^n(X-i) \in \mathbb{R}_{n-1}[X]$. Because $Q$ is orthogonal to every polynomial in $\mathbb{R}_{n-1}[X]$ we have,
$$\forall 1\leq\ell\leq n, \langle Q |Q_{\ell} \rangle =0$$
thus for $1\leq\ell\leq n$,
$$\sum_{i=0}^{n} Q(i)Q_{\ell}(i) =0$$
So,
$$Q(\ell)Q_{\ell}(\ell)+Q(0)Q_{\ell}(0)=0$$
Thus,
$$\forall 1 \leq \ell \leq n, \quad Q(\ell) = -\frac{Q_{\ell}(0)}{Q_{\ell}(\ell)} Q(0) = -\frac{(-1)^{n-1}n!/\ell}{(\ell-1)!(-1)^{n-\ell}(n-\ell)!}Q(0) = (-1)^{\ell} \binom{n}{\ell}Q(0)$$
And this result is also true when $\ell=0$.
We can deduce that,
$$\lVert Q \rVert^2 = \sum_{i=0}^n Q(i)^2 = \sum_{i=0}^n \binom{n}{i}^2 Q(0)^2 =Q(0)^2 \sum_{i=0}^n \binom{n}{i}^2 $$
Moreover using Lagrange polynomials,
$$Q = \sum_{\ell=0}^{n}Q(\ell) \prod_{\substack{i=0\\i \neq \ell}}^n\dfrac{X-i}{\ell-i}$$
We can see that the coefficient before $X^n$ in $Q$ is $1$ ($Q$ is monic) but also:
$$ \sum_{\ell=0}^{n}Q(\ell) \prod_{\substack{i=0\\i \neq \ell}}^n\dfrac{1}{\ell-i} = 1 $$
Therefore,
$$ \sum_{\ell=0}^n (-1)^{\ell} \binom{n}{\ell}Q(0) \dfrac{(-1)^{n-\ell}}{\ell! (n-\ell)!}=1 $$
Hence,
$$(-1)^n \dfrac{Q(0)}{n!} \sum_{\ell=0}^{n} \binom{n}{\ell}^2 = 1$$
So,
$$Q(0) = (-1)^n n! \left(\sum_{\ell=0}^{n} \binom{n}{\ell}^2\right)^{-1}$$
By expanding $(1+X)^{2n} = (1+X)^n(1+X)^n$ with binomial expansion and identifying the term before $X^n$, we end up with:
$$\sum_{\ell=0}^{n} \binom{n}{\ell}^2 = \binom{2n}{n} = \dfrac{(2n)!}{(n!)^2} $$
Therefore,
$$\lVert Q \rVert^2 = \left((-1)^n n! \left(\sum_{\ell=0}^{n} \binom{n}{\ell}^2\right)^{-1} \right)^2 \sum_{\ell=0}^{n} \binom{n}{\ell}^2 = (n!)^2 \dfrac{(n!)^2}{(2n)!}=\dfrac{(n!)^4}{(2n)!}$$
To conclude,
$$\boxed{\min_{P \in \mathbb{R}_{n-1}[X]} \left( \displaystyle\sum_{i=0}^n(i^n-P(i))^2 \right) = \dfrac{(n!)^4}{(2n)!}}$$