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}?$

|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny69822844