For all natural numbers $a_i$ of the set $\{1,2,\dots\,2017\}$ show that $\sum_{i=1}^{2017}\frac{{a_i}^2-i^2}{i} \geq 0$ For all natural numbers $a_i$ of the set $\{1,2,\dots\,2017\}$:
Show that:
My try:
First , I considered the obvious case where $\forall$ $ i \in \{1,2,\dots,2017\}$: $a_i=i$
Then : $S=0$
Further more I considered the edge case where $a_i=2018-i$
(My motivation here was to assume the Sum would be most minimized)
That way $$S=\sum_{i=1}^{2017}\frac{(2018-i)^2-i^2}{i}$$
$\Longleftrightarrow$
$$S=\sum_{i=1}^{2017}\frac{2018^2-4036i}{i}$$
$\Longleftrightarrow$
$$S=-4036\times2017+\sum_{i=1}^{2017}\frac{2018^2}{i}$$
Clearly $S > 0$
However my proofs lacks an atrocious amount of rigor as it doesn't treat a  general case and doesn't spit out an obvious answer.
My idea here was to prove that $Min(S)$ is achieved  when $a_i=i$ but i have failed to do so.
 A: Assuming that $\{a_1,\ldots,a_{2017}\}$ is a permutation of $\{1, \ldots, 2017\}$, this is a direct application of Titu's Lemma, a consequence of Cauchy-Schwarz:
$$
\sum\limits_{i=1}^{n} \frac{a_i^2}{i} \geq \frac{\left(\sum\limits_{i=1}^{n} a_i\right)^2}{\sum\limits_{i=1}^{n} i} = \sum\limits_{i=1}^{n} i = \sum\limits_{i=1}^{n} \frac{i^2}{i}
$$
which clearly implies the conclusion.
A: Let's apply Rearrangement inequality for sequences $1^2 <2^2 <\cdots < 2007^2$ and $\dfrac{1}{1}> \dfrac{1}{2}>\cdots >\dfrac{1}{2007}$; $$ \sum_{i=1}^{2007} \dfrac{a_i^2}{i} \geq \sum_{i=1}^{2007} \dfrac{i^2}{i} $$
Hence, we get $$ \sum_{i=1}^{2007} \dfrac{a_i^2 -i^2}{i} \geq \sum_{i=1}^{2007} \dfrac{i^2 -i^2}{i} = 0 .$$
A: Let $S(a) = \sum_{i=1}^{n}\frac{{a_i}^2-i^2}{i}$, where $a$ is a permutation of the integers from $1$ to $n$ inclusive.
When $n = 1$, we trivially have $S([1]) = 0$.
When $n = 2$, there are 2 possible permutations:
$$S([1, 2]) = 0$$
$$S([2, 1]) = \frac{3}{2} = 1.5$$
When $n = 3$, there are $3! = 6$ possible permuations:
$$S([1, 2, 3]) = 0$$
$$S([1, 3, 2]) = \frac{5}{6} = 0.8333333...$$
$$S([2, 1, 3]) = \frac{3}{2} = 1.5$$
$$S([2, 3, 1]) = \frac{17}{6} = 2.8333333...$$
$$S([3, 1, 2]) = \frac{29}{6} = 4.8333333...$$
$$S([3, 2, 1]) = \frac{16}{3} = 5.333333...$$
Conjecture #1: $S(a)$ obtains a minimum value of zero when $a$ is in ascending order.
Conjecture #2: $S(a)$ obtains its maximum value when $a$ is in descending order.
The above examples provide a “brute-force” proof for $n = 1, 2, 3$.  However, unless you have the computing power to evaluate $2017! \approx 4.69 \times 10^{5791}$ permutations, this approach won't work for $n = 2017$.  So let's try something different.
Let $a$ and $b$ be two permutations of the integers from $1$ to $n$, that are identical except at index $i$ and $j$ (and WLOG, take $i < j$), where the values are swapped.
$$a_i = c, a_j = d$$
$$b_i = d, b_j = c$$
Then
$$S(b) - S(a) = \frac{d^2-i^2}{i} + \frac{c^2-j^2}{j} - \frac{c^2-i^2}{i} - \frac{d^2-j^2}{j} = \frac{(d^2 - c^2)(j - i)}{ij}$$
Since $j - i$ and $ij$ are both positive, this difference's sign depends on $d^2 - c^2$.  IOW,
$$S(a) < S(b) \text{ iff } c < d$$
$$S(a) > S(b) \text{ iff } c > d$$
So, for any specific $(i, j)$ pair, we can locally minimize $S$ by having $a_i < a_j$.  By applying a sorting network to the entire permutation, we can globally minimize $S$ by having its permutation in ascending order, $a_i = i$, in which case $S(a) = 0$ trivially follows from its definition.
