# Dorin Marghidanu's Permuted Inequality

### Solution 1

Let $s=nk.$ Since, for $p\ge 1,$ function $x^p$ is convex on $(0,\infty),$ we have

\displaystyle \begin{align} \sum_{k=1}^n\left(a_k+\frac{1}{a_{\sigma(k)}}\right)^p&\ge\frac{1}{n^{p-1}}\left[\sum_{k=1}^n\left(a_k+\frac{1}{a_{\sigma(k)}}\right)\right]^p\\ &=\frac{1}{n^{p-1}}\left[\sum_{k=1}^na_k+\sum_{k=1}^n\frac{1}{a_{\sigma(k)}}\right]^p\\ &=\frac{1}{n^{p-1}}\left[nk+\sum_{k=1}^n\frac{1}{a_{k}}\right]^p. \end{align}

Now, by the AM-HM inequality,

\displaystyle\begin{align}&\sum_{k=1}^n\frac{1}{a_k}\ge\frac{n}{k}&\Rightarrow\\ &\frac{1}{n^{p-1}}\cdot\left[nk+\sum_{k=1}^n\frac{1}{a_k}\right]^p\ge\frac{n(k^2+1)^p}{k^p}=\frac{(s^2+n^2)^p}{n^{p-1}s^p}. \end{align}

### Solution 2

By the power-mean inequality, $\displaystyle \left(\frac{1}{n}\sum_{k=1}^na_k^p\right)^{\frac{1}{p}}\ge\frac{1}{n}\sum_{k=1}^na_k,$ so that

(1)

$\displaystyle \sum_{k=1}^na_k\ge\frac{1}{n^{p-1}}\left(\sum_{k=1}^na_k\right)^p.$

(with equality if $a_1=\ldots=a_n.)$ Hence,

\displaystyle\begin{align}\sum_{k=1}^n\left(a_k+\frac{1}{a_{\sigma(k)}}\right)^p&\ge\frac{1}{n^{p-1}}\left[\sum_{k=1}^n\left(a_k+\frac{1}{a_{\sigma(k)}}\right)\right]^p\\ &=\frac{1}{n^{p-1}}\left(s+\sum_{k=1}^n\frac{1}{a_k}\right)^p, \end{align}

i.e.,

(2)

$\displaystyle\sum_{k=1}^n\left(a_k+\frac{1}{a_{\sigma(k)}}\right)^p\ge\frac{1}{n^{p-1}}\left(s+\sum_{k=1}^n\frac{1}{a_k}\right)^p.$

With equality if

(E1)

$\displaystyle a_1+\frac{1}{a_{\sigma(1)}}=\ldots=a_n+\frac{1}{a_{\sigma(n)}}.$

Also, using the AM-HM inequality,

$\displaystyle \frac{1}{n}\sum_{k=1}^na_k\ge\frac{n}{\displaystyle \frac{1}{a_1}+\ldots+\frac{1}{a_n}},$

implying

(3)

$\displaystyle \frac{1}{a_1}+\ldots+\frac{1}{a_n}\ge\frac{n^2}{a_1+\ldots+a_n}=\frac{n^2}{s},$

with equality if

(E2)

$\displaystyle a_1=a_2=\ldots=a_n\;\left(=\frac{s}{n}\right).$

From (2) and (3) we obtain

$\displaystyle \sum_{k=1}^n\left(a_k+\frac{1}{a_{\sigma(k)}}\right)^p\ge\frac{1}{n^{p-1}}\left(s+\frac{n^2}{s}\right)^p=\frac{(s^2+n^2)^p}{n^{p-1}s^p},$

with equality $a_1=a_2=\ldots=a_n.$ Note that (E2) implies (E1).

### Solution 3

Applying first the power-mean inequality and, subsequently, Bergstrom's inequality, we get

\displaystyle \begin{align} \sum_{k=1}^n\left(a_k+\frac{1}{a_{\sigma(k)}}\right)^p&\ge n\left(\frac{\displaystyle \sum_{k=1}^na_k+\sum_{k=1}^n\frac{1}{a_k}}{n}\right)^p\\ &\ge\frac{\displaystyle \left(s+\frac{(1+1+\ldots+1)^2}{a_1+a_2+\ldots+a_n}\right)^p}{n^{p-1}}\\ &=\frac{\displaystyle \left(s+\frac{n^2}{s}\right)^p}{n^{p-1}}=\frac{(s^2+n^2)^p}{n^{p-1}s^p}. \end{align}

### Solution 4

We have by the power-mean inequality:

$\displaystyle \sum _{i=1}^n \left(\frac{1}{a_{\sigma _i}}+a_i\right)^p\geq n^{1-p} \left(\sum _{i=1}^n a_i+\frac{1}{a_{\sigma _i}}\right)^p= n^{1-p} \left(s + \sum _{i=1}^n \frac{1}{a_{i}}\right)^p$

since

$\displaystyle \left(\sum _{i=1}^n \frac{\left(\frac{1}{a_{\sigma _i}}+a_i\right){}^p}{n}\right)^{1/p}\geq \sum _{i=1}^n \frac{\frac{1}{a_{\sigma _i}}+a_i}{n}$ and $p\geq 1$.

We have

$\displaystyle lhs \geq n^{1-p} \left(\sum _{i=1}^n a_i+\frac{1}{a_{i}}\right)^p= n^{1-p} \left(s + \sum _{i=1}^n \frac{1}{a_{i}}\right)^p$

By the arithmetic-harmonic mean inequality,

$\displaystyle \frac{1}{n}\sum _{i=1}^n a_i\geq \frac{n}{\displaystyle \sum _{i=1}^n \frac{1}{a_i}}$, $\sum _{i=1}^n \frac{1}{a_i}\geq \frac{n^2}{\displaystyle \sum _{i=1}^n a_i}=\frac{n^2}{s}$.

Replacing we get $\displaystyle lhs\geq \frac{1}{n^{p-1} s^p} \left(n^2+ s^2\right)^p$

as required.

### Acknowledgment

Dorin Marghidanu has kindly posted the problem at the CutTheKnotMath facebook page, with several solutions. Solution 1 is by Leo Giugiuc, Solution 2 is by Dorin Marghidanu; Solution 3 is by Daniel Dan; Solution 4 is by N. N.Taleb.