Lower bound of the sum of some natural numbers

Question

Let $a_1,a_2,\ldots, a_n$ be $n$ distinct positive odd integers. Suppose that all the differences $$|a_i-a_j|,\;\;\;\;\;1\leq i<j\leq n$$are distinct. Then prove that the following inequality is true.$$ a_1+a_2+\dots+a_n\geq \frac{n(n^2+2)}{3}$$

---

All I could do is a following:

Let $m ={n\choose 2}$ and

$$ I := \sum_{i\ne j} |a_i-a_j| \geq \sum _{i=1}^m i = {m(m+1)\over 2}$$

On the other hand (since $|x-y|\leq x+y$) we have $$I \leq (a_1+a_2+\dots+a_n)(n-1)$$ So we have $$a_1+a_2+\dots+a_n \geq {n(n^2-n+2)\over 4}$$ which is pretty weaker bound than desired one.

Answer 1

Hint: Show that $a_1 + a_2 + \dots +a_n \geq 1+3+7+13+\dots+n^2-n+1$.

Answer 2

Without loss of generality we may, and will, assume that $a_1<a_2<\cdots<a_n$. The numbers $(a_{k}-a_{k-1})_{k=2,\ldots,j}$ are distinct even integers, so their sum is larger or equal to the sum of the first $j-1$ even integers which is $(j-1)j$ so $$a_{j}\ge a_1+j(j-1)\ge 1-j+j^2\qquad j=1,\ldots,n$$ Adding we get the desired result.