Inequality for Integer Sequences

Leo Giugiuc posted an elegant problem and its solution at the CutTheKnotMath facebook page. The problem is by Professor Laurentiu Panaitopol; the solution by the team of Claudia Nanuti, Diana Trailescu, Dan Sitaru and Leo Giugiuc.

Let $a_1,a_2,\ldots,a_n$ be pairwise distinct positive integers. Then

$\displaystyle\sum_{k=1}^{n}a_{k}^{2}\ge\frac{2n+1}{3}\sum_{k=1}^{n}a_{k},$

with equality only when $a_1,a_2,\ldots,a_n$ is a permutation of $1,2,\ldots,n.$

Proof

Denote the left-hand side of the inequality $L(n),$ the right $R(n)$ and assume without loss of generality that the sequence $\{a_{k}\}$ is increasing.

The proof is by induction.

The claim is obvious for $n=1.$ Assume it holds for some $n,$ i.e., $L(n)\ge R(n),$ and prove it for $n+1,$ i.e., $L(n+1)\ge R(n+1).$ We shall prove more, viz., $L(n+1)-L(n)\ge R(n+1)-R(n)$ which together with $L(n)\ge R(n)$ implies $L(n+1)\ge R(n+1).$

Observe that $L(n+1)-L(n)=a_{n+1}^{2},$ while

$\displaystyle\begin{align} R(n+1)-R(n)&=\frac{2n+3}{3}\sum_{k=1}^{n+1}a_{k}-\frac{2n+1}{3}\sum_{k=1}^{n}a_{k}\\ &=\frac{2}{3}\sum_{k=1}^{n}a_{k}+\frac{2n+1}{3}a_{n+1}. \end{align}$

Observe that, since we deal with integer sequences, for all $s$ and $t,$ $a_{s+t}\ge a_{s}+t,$ or $a_{s}\le a_{s+t}-t.$ In particular, $a_{n+1-k}\le a_{n+1}-k.$ Instead of proving $a_{n+1}^{2}\ge R(n+1)-R(n),$ we'll prove a stronger inequality

$\displaystyle\begin{align} a_{n+1}^{2}&\ge\frac{2}{3}\sum_{k=1}^{n}(a_{n+1}-k)+\frac{2n+1}{3}a_{n+1}\\ &=\frac{2n}{3}a_{n+1}-\frac{2}{3}\frac{n(n+1)}{2}+\frac{2n+1}{3}a_{n+1}\\ &=\frac{4n+1}{3}a_{n+1}-\frac{2}{3}\frac{n(n+1)}{2}. \end{align}$

The latter inequality is equivalent to

$\displaystyle 3a_{n+1}^{2}-(4n+1)a_{n+1}+n(n+1)\ge 0.$

The left-hand side allows for factoring

$\displaystyle 3a_{n+1}^{2}-(4n+1)a_{n+1}+n(n+1)=(3a_{n+1}-n)(a_{n+1}-(n+1)).$

which makes the inequality obvious because $a_{n+1}\ge n+1.$ This is also the only case where we get an equality.

As an add-on, under the conditions of the above problem, is it true that

$\displaystyle\sum_{k=1}^{n}a_{k}^{3}\ge\frac{n(n+1)}{2}\sum_{k=1}^{n}a_{k}?$

65403139