Inequality proof $\left( \sum_{i \in S} x_i \right)^2 \le \sum_{1 \le i \le j \le n} (x_i + \cdots + x_j)^2$ I want to show that for any non-empty set $S \subseteq \{1,2, \ldots, n \}$ we have $$\left( \sum_{i \in S} x_i \right)^2 \le \sum_{1 \le i \le j \le n} (x_i + \cdots + x_j)^2 \qquad x_i \in \mathbb R, \ n \ge 2$$
I have looked at some special cases and the result seems somewhat obvious but I am struggling to prove it. Maybe induction?
 A: This is Romania Team Selection Test 2004, Problem 12. Here is the solution I posted on the Art of Problem Solving forums.
We proceed by induction on $n \ge 1$ (but the induction is superficial here; it's just to formalize an optimization argument), with base case $n=1$ being immediate. Now for a given $n$ we consider the following three cases.
If there is $k$ such that $k, k+1 \in S$, then we can reduce to the $n-1$ case by combining $x_k + x_{k+1}$ into a single variable, discarding the terms of the right-hand side which contain exactly one of the two.  Similarly, if $k, k+1 \notin S$ (even $k=0$ and $k=n$) then we again reduce to $n-1$ by the same technique.
Thus by doing the above optimizations, the only case left to consider is $n$ odd and $S = \{1, 3, 5, \dots, n\}$. Denote $y_k = x_1 + \dots + x_k$ for $0 \le k \le n$, then this reduces to the inequality
$$
 \left( y_n - y_{n-1} + y_{n-2} - y_{n-3} + \dots + y_1 - y_0 \right)^2
 \le
 \sum_{0 \le i < j \le n} (y_j - y_i)^2.
$$
If we expand this, we can rewrite the inequality as
$$ 
 \sum_{\substack{0 \le i < j \le n \\ i+j \text{ even}}} y_iy_j
 \le \frac{n-1}{4} \sum_{0 \le i \le n} y_i^2.
 $$
But this follows by simply summing the two obvious inequalities
$$ 
 \sum_{\substack{0 \le i < j \le n \\ i,j \text{ even}}} y_iy_j
 \le \frac{n-1}{4} \sum_{\substack{0 \le i \le n \\ i \text{ even}}} y_i^2
 \qquad\text{and}\qquad
 \sum_{\substack{0 \le i < j \le n \\ i,j \text{ odd}}} y_iy_j
 \le \frac{n-1}{4} \sum_{\substack{0 \le i \le n \\ i \text{ odd}}} y_i^2.
$$.
