Inequality for Integer Sequences II

The problem below is an afterthought following an earlier page with the solution supplied at the CutTheKnotMath facebook page 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


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


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-1,$ i.e., $L(n-1)\ge R(n-1),$ and prove it for $n,$ i.e., $L(n)\ge R(n).$ We shall prove more, viz., $L(n)-L(n-1)\ge R(n)-R(n-1)$ which together with $L(n-1)\ge R(n-1)$ implies $L(n)\ge R(n).$

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

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

Note, as before, 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-k}\le a_{n}-k.$ Instead of proving $a_{n}^{2}\ge R(n)-R(n-1),$ we'll prove a stronger inequality

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

The latter inequality is equivalent to

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

The left-hand side allows for factoring

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

which makes the inequality obvious because $a_{n}\ge n.$ Also, $a_{n}=n$ is the only case where we get an equality.

In all likelihood, for all strictly increasing sequences of positive integers (or their permutations) we have, for $v\gt u,$

$\displaystyle \sum_{k=1}^{n}k^u \sum_{k=1}^{n}a_{k}^v\ge \sum_{k=1}^{n}k^v \sum_{k=1}^{n}a_{k}^u,$

or even, for $a_{k}\ge b_{k},$

$\displaystyle \sum_{k=1}^{n}b_{k}^u \sum_{k=1}^{n}a_{k}^v\ge \sum_{k=1}^{n}b_{k}^v \sum_{k=1}^{n}a_{k}^u,$

which holds for positive real numbers, not necessarily integers or pairwise distinct.

More accurately,

For real $a_{k}\ge b_{k}\ge 1,$ $k=1,\ldots ,n$ and $v\ge u\gt 0,$

$\displaystyle \sum_{k=1}^{n}b_{k}^u \sum_{k=1}^{n}a_{k}^v\ge \sum_{k=1}^{n}b_{k}^v \sum_{k=1}^{n}a_{k}^u,$

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny