# 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.

• What about the case where all $a_i = 1$? Shouldn't that give a counterexample? (Or are you actually requiring that $a_1, \ldots, a_{2017}$ are a permutation of $1, \ldots, 2017$?) Nov 28, 2022 at 21:50
• Nov 28, 2022 at 22:12

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.

• Brilliant ! I should have thought about famous inequalities . I'll try to train my intuition to unravel the answers more quickly . Thanks for everyone's dedicated effort to posting a solution! Nov 29, 2022 at 12:17

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 .$$

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() = 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.

• That is essentially the proof of the rearrangement inequality :) Nov 29, 2022 at 8:49