# Prove the inequality $x_1^{y_1}+x_2^{y_2}+\cdots+x_n^{y_n} \geq x_1^{y_{\pi(1)}}+x_2^{y_{\pi(2)}}+\cdots+x_n^{y_{\pi(n)}}.$

Let $1 \leq x_1 \leq x_2 \leq \cdots \leq x_n$ and $1 \leq y_1 \leq y_2 \leq \cdots \leq y_n$. For any permutation $\pi$ prove the inequality $$x_1^{y_1}+x_2^{y_2}+\cdots+x_n^{y_n} \geq x_1^{y_{\pi(1)}}+x_2^{y_{\pi(2)}}+\cdots+x_n^{y_{\pi(n)}}.$$ Seems it is a kind of rearrangement inequality but I have no idea how to prove it.

This can be considered a special case of the more general rearrangement result: for real functions $f_1, f_2, \dots, f_n$ defined on $I$ s.t. $f_{k+1}-f_k$ is increasing on $I$ for each allowable $k$, then for any non-decreasing sequence $x_k \in I$ , $$\sum_k f_i(x_{n+1-k}) \le \sum_k f_k(x_{\pi k}) \le \sum_k f_k(x_k)$$ where $\pi$ is any permutation. A proof can be found at AMM Vol. 97, No. 4 (Apr, 1990), pp. 319-323

Here we take $f_k(x) = x^{y_k}$ and use the right inequality.

Hint:

Take note of the fact that you can generate any permutation in a finite number of steps consisting of swapping only two elements.

Using this, can you think of a way of proving this by induction?

Edit: Let $P_m:=\left\{\pi: \pi \text{ is a permutation of }1,...,n \wedge \text{ the largest index changed is }m\right\}$

Quite obviously, $\bigcap_{m\in\mathbb{N}}{P_m}\supset P_n$ includes all permutations, so we can used induction:

$P_0=\left\{id\right\}$, so the statement holds.

For typing reasons, let us write $F(\pi)$ for the left hand side of your original inequation.

Assume, given any natural $m$, the inequality holds for all $\pi\in P_m$.

We want to show that the inequality is also true for all $\pi\in P_{m+1}$.

More precisely, given such a $\pi$, we want to show that

$x_1^{y_1}+...+x_n^{y_n}\geq x_1^{y_1}+...+x_{m+1}^{\pi(y_{m+1})}+...+x_1^{\pi(y_1)}\Leftrightarrow F(id)\geq F(\pi)$.

Now, think of the permutation \begin{align} \pi'(n)=\begin{cases} \pi(n)&n\neq m+1, \pi(m+1)\\ m+1&n=m+1\\ \pi(m+1) &n=\pi(m+1) \end{cases} \end{align}

Now, all we need to do is show that $F(\pi')\geq F(\pi)$, and our induction would be finished. And that proof is actually quite short, can you think of a way to do so?

Edit 2:

Given $n=3,m=2$.

We assume that for any permutation which leaves $k\geq 3$ be, our statement holds.

Now, given any permutation which leaves $k\geq m+1=4$ be, which in this case is literally any permutation, we want to show that the inequality still holds.

The way we define our permutation $\pi'$ is as follows:

We take the largest index changed, namely $3$, and give it back its original value by exchanging it with the appropriate number. Say, for example, $\pi=(1,2,3)\mapsto (2,3,1)$.

Then we would have $\pi'=(1,2,3)\mapsto (1,3,2)$.

Put differently, we have the inequality

$x_1^{y_1}+x_2^{y_2}+x_3^{y_3}\geq x_1^{y_2}+x_2^{y_3}+x_3^{y_1}$,

and inserting our $\pi'$ we can prove this using the above assumption by writing

$x_1^{y_1}+x_2^{y_2}+x_3^{y_3}\geq x_1^{y_1}+x_2^{y_3}+x_3^{y_2}\geq x_1^{y_2}+x_2^{y_3}+x_3^{y_1}$

Edit 3: Also, I might be somewhat inconsistent in whether the largest or smallest index changed is used as the index. It should be the index closest to the maximum number, but in my notes I somehow used $x_n\geq...\geq x_1$ - might get around to change that at some point, but the idea works either way - just so you are aware of that...

• I dont see how to realise this idea even for the case $n=3$ with assuming that the case $n=2$ holds. – Leox Jun 14 '15 at 20:07
• I don't actually mean induction for $n$. You can use induction on the permutation; eg let $m$ be the least number of swaps needed to produce any given permutation, and then work with that. Does that help? Otherwise, I can include an outline of the actual proof. – Some Math Student Jun 14 '15 at 20:10
• Ok, let $n=3$ and $m=2$. How to prove it? – Leox Jun 14 '15 at 20:12
• Better argue in a similar way to the proof of Theorem 1 in artofproblemsolving.com/community/c6h288335p1798111 . (You will now need to check that $a^b + c^d \leq a^d + c^b$ if $1 \leq c \leq a$ and $1 \leq b \leq d$ to get the analogue of my equality (3). This is easily done using derivatives (for $b, d$ real) or the geometric series (for $b, d$ positive integers).) I have always been wary of the swap-two-elements argument due to its ability to run around in circles if one doesn't pay attention; my proof linked above doesn't share this downside. – darij grinberg Jun 14 '15 at 20:32
• As a matter of fact, my definition of the induction was slightly imprecise. You can use an iterative approach as I stated, but the number of swaps needed is not an ideal way to order the permutations. Which, incidentally, leads to something fairly similar to the proof mentioned in the comment above. – Some Math Student Jun 14 '15 at 20:43