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$

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.