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)}}.$

Question

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.

Answer 1

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.

Answer 2

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...