
> 
> Let $n$ be a positive integer. Determine the smallest possible value of $|p(1)|^2+|p(2)|^2 +...+ |p(n+3)|^2$ over all monic polynomials $p$ of degree $n$.
> 
> 
> 


This question was proposed (problem A.611)
some time ago at [KoMaL](http://www.komal.hu/verseny/feladat.cgi?a=feladat&f=A611&l=en).  

The minimal values for $n=0,1,2,3$ are $3,5,14,324/5$.  

It was also discussed at [math.se](https://math.stackexchange.com/questions/796808/minimising-an-expression-involving-polynomial), where the polynomial minimising such sum was found using Gram-Schmidt algorithm.  

However the minimum value was not determined.


Any suggestion is welcome.



Minimum value of $|p(1)|^2+|p(2)|^2 +...+ |p(n+3)|^2$ over all monic polynomials $p$
[*edited* to explain a few steps and connect with the Hahn polynomials]


The answer is
$$
\frac{(2n+1)(2n+3) n!^4}{(2n)!}
$$
assuming that I did the algebra right, which seems likely because this formula
agrees with the previously computed values $3,5,14,324/5$ for $n=0,1,2,3$.


Consider first the minimum of $\sum\_{i=1}^{n+1} p(i)^2$ over monic $p$
of degree $n$. Any vector $v = (a\_1,a\_2,\ldots,a\_{n+1})$ is the list of
values at $1,2,\ldots,n+1$ of some polynomial of degree at most $n$;
the leading coefficient of this polynomial is $(u,v) / n!$ where
$u$ is the vector whose $(n+1-i)$-th coordinate is $(-1)^i {n \choose i}$
(each $i$ in $0 \leq i \leq n$).$\color{red}{\bf[1]}$
We thus seek the minimum of $(v,v)$ subject to $(u,v) = n!$, 
and by Cauchy-Schwarz the answer is $n!^2 / (u,u)$, attained **iff**
$v = n! u / (u,u)$. The denominator $(u,u)$ is $\sum\_{i=0}^n {n \choose i}^2$,
which is well-known to equal $2n \choose n$.$\color{red}{\bf[2]}$
Hence the answer is $n!^2 / {2n \choose n} = n!^4 / (2n)!$.


With a bit more work we can find for each $k$ the minimum of
$\sum\_{i=1}^{n+k+1} p(i)^2$ over monic $p$ of degree $n$.
Here's how it goes for $k=2$. There are now three linear conditions
on $v = (a\_1,a\_2,\ldots,a\_{n+3})$ to be the list of values at
$1,2,\ldots,n+3$ of a monic polynomial of degree at most $n$.
We can write them as $(u\_0,v)=n!$, $(u\_1,v)=0$, $(u\_2,v)=0$,
where $u\_j$ is the vector whose $(n+3-i)$-th coordinate is
$(-1)^i {n+j \choose i}$ for each $i$ in $0 \leq i \leq n+2$.$\color{red}{\bf[1a]}$
As was the case for $k=0$,
the minimum of $(v,v)$ over all such $v$ is attained by
a linear combination of $u\_0,u\_1,u\_2$. So we need only
calculate the $3 \times 3$ Gram matrix of inner products
$(u\_j,u\_{j'})$ $(j,j'=0,1,2)$, and invert it to find the linear combination
$v$ such that $(u\_j,v) = n! \delta\_j$. Each $(u\_j,u\_{j'})$ is
$\sum\_{i \geq 0} {n+j \choose i} {n+j' \choose i} 
 = {2n+j+j' \choose n+j}$.$\color{red}{\bf[2a]}$
So write each of these entries of the Gram matrix as $2n \choose n$ times
some rational function of $n$, solve the resulting linear equations for
the coefficients of $v$ in $u\_0,u\_1,u\_2$, and recover $(v,v)$.
This calculation yields the formula $(2n+1)(2n+3) n!^2 / {2n \choose n}$
displayed (in equivalent form) at the start of this answer.


For general $k$ the minimum seems to be
$$
\frac{n!^4}{(2n)!} {2n+1+k \, \choose k},
$$
which presumably can be proved from the above analysis
 and known identities.$\color{red}{\bf[3]}$




---


$\color{red}{\bf[1],[1a]}$ Taking the inner product with $u$ 
 amounts to evaluating an $n$-th finite difference.
Likewise, taking the inner product with $u\_i$ amounts to evaluating
 an $(n+i)$-th finite difference.


$\color{red}{\bf[2],[2a]}$ The formula
$\sum\_{i \geq 0} {m \choose i} {m' \choose i} = {m+m' \choose m}$
has at least two well-known proofs, one bijective and one
[generatingfunctionological](https://www.math.upenn.edu/~wilf/DownldGF.html).
For the former, write ${m+m' \choose m}$ as the number of $(m+m')$-tuples
of $m$ 0's and $m'$ 1's, and let $i$ be the number of 1's among the
first $m$ coordinates. For the latter, compute the $X^m$ coefficient 
of $(1+X)^m \, (1+X)^{m'} = (1+X)^{m+m'}$ in two ways.


$\color{red}{\bf[3]}$ Further corroboration is that this is also 
consistent with the extreme cases $n=0$ and (with a bit more work) $n=1$.
I later obtained a proof by transforming the relevant determinants into 
Vandermonde determinants. The existence of such a formula for all $n,k$ 
suggested that the $p$'s (which are orthogonal polynomials for a 
discrete measure) must be known already, and after some Googling 
found that indeed they are the special case $\alpha=\beta=0$ of the 
[Hahn polynomials](https://en.wikipedia.org/wiki/Hahn_polynomials)
$Q\_n$ evaluated at $x-1$ (with $N = n+k+1$). The orthogonality relation,
together with the formula for the leading coefficient of $Q\_n$,
soon yields the evaluation for all $n,k$ of the minimum of 
$\sum\_{i=1}^{n+k+1} p(i)^2$ over monic polynomials $p$ of degree $n$.


