Inequality for a sorted set Given $X = \{x_1, x_2, \cdots, x_n\}, n \geq2$ such that $x_1 \lt x_2 \lt \cdots \lt x_n$, could you prove:
$
\frac{1}{n^2}\sum_{1 \leq i \lt j \leq n}(x_i - x_j)^2 \leq \frac{(x_1 - x_n)^2}{4}
$
I can easily prove for $n=2, 3, 4, 5$, but I'm failed to do it for an arbitrary $n$.
 A: WLOG, fix $x_1=0,x_n=1.$
$f(x_2,\cdots,x_{n-1}):=\frac{1}{2}\sum_{1\le i<j\le n}(x_i-x_j)^2.$ We only need to prove that $f_{\max}\le \frac{n^2}{8}$ in the area $\{(x_2,\cdots,x_{n-1})|0<x_2<\cdots<x_{n-1}<1\}.$
$$\partial_l f=\sum_{l<j\le n}(x_l-x_j)-\sum_{1\le i<l}(x_i-x_l),\quad\partial_{ls} f=\begin{cases}-1&l\neq s\\ n-1 &l=s\end{cases}.$$
As the Hessian matrix is strictly diagonally dominant, it's positive definite. So the maximum is achieved at the boundary. Inductively, one can show that $f_{\max}=f(0,\cdots,0,1,\cdots,1).$ (The vertex of the convex area $\{(x_2,\cdots,x_{n-1})|0<x_2<\cdots<x_{n-1}<1\}.$)
Back to the inequality, Assume we have $x_1=\cdots=x_m=0,$ $x_{m+1}=\cdots=x_n=1.$
$$
\sum_{1\le i<j\le n}(x_i-x_j)^2=m(n-m)\le \frac{n^2}{4}.
$$
This proved the original inequality.
A: Alternative proof:
Fixed $x_1, x_n$ ($x_1 < x_n$), let us find the maximum of
$$f(x_2, x_3, \cdots, x_{n - 1}) = \frac{1}{n^2}\sum_{1\le i < j\le n} (x_i - x_j)^2$$
subject to $x_1 \le x_2 \le x_3 \le \cdots \le x_{n - 1} \le x_n$.
We claim that at maximum, there exists $k$ such that
$x_1 = x_2 = \cdots = x_k < x_{k + 1} = x_{k + 2} = \cdots = x_n$.
Assume, for the sake of contradiction, that at maximum, $x_m < x_{m + 1} = \cdots = x_{m + r} < x_{m + r + 1}$ for some $m, r$.
Let
$$g(t) = f(x_1, \cdots, x_m, t, \cdots, t, x_{m + r + 1}, \cdots, x_n).$$
It is not difficult to prove that
$g(t)$ is strictly convex.
Thus, $g(x_{m + 1}) < \max(g(x_{m}), \, g(x_{m + r + 1}))$.
Contradiction.
With $x_1 = x_2 = \cdots = x_k < x_{k + 1} = x_{k + 2} = \cdots = x_n$, we have
$$f(x_2, x_3, \cdots, x_{n - 1}) = 
\frac{1}{n^2}(n - k)k (x_1 - x_n)^2 \le \frac{(n - k + k)^2}{4n^2}(x_1 - x_n)^2 = \frac{(x_1 - x_n)^2}{4}.$$
We are done.
