# Rearrangement Inequality Theorem - Proof

The theorem states that the sum $$S=a_1b_1 + . . . + a_nb_n$$ is a maximum if two strings $$a_1,...,a_n$$ and $$b_1,...,b_n$$ have the same order. Let's assume $$a_1 and $$b_1. The proof from my book is this one ( the same I sensed at the first glance):

Let $$a_r>a_s (b_r>b_s)$$. Consider the sums:

$$S_1=a_1b_1+...+a_rb_r+...+a_sb_s+...+a_nb_n,$$

$$S_2=a_1b_1+...+a_rb_s+...+a_sb_r+...+a_nb_n.$$

We obtain $$S_2$$ from $$S_1$$ by replacing $$b_s$$ with $$b_r$$. Hence

$$S_2-S_1=a_rb_s+a_sb_r-a_rb_r-a_sb_s=(a_r-a_s)(b_s-b_r)<0$$

We deduce that $$S_1>S_2$$.

This is their proof. But it's not enough for me because of this: Let's assume the strings are big enough and have at least one element between the positions $$r$$ and $$s$$ in the strings ( denoted by $$i$$, $$r ), where $$a_1<... and $$b_1<.... The only way through which we can obtain from $$S_2$$ a bigger sum than $$S_2$$ using rearrangements is to interchange $$b_r$$ with the "$$b$$ factor" of one of the terms between $$a_rb_s$$ and $$a_sb_r$$ in $$S_2$$, i.e. $$b_i$$. By doing this we obtain the following sum from $$S_2$$:

$$S_3=a_1b_1+...+a_rb_s+...+a_ib_r+...+a_sb_i+...+a_nb_n.$$

This sum is bigger than $$S_2$$ if you try to prove it. Even though I could prove that $$S_3>S_1$$, it is pointless as my aim is to find the generalization in their proof or at least another general one, but I just can't seem to succeed. I hope you could help me with a proof for this problem. Thanks in advance!

• here you can find a proof artofproblemsolving.com/wiki/… Commented Jul 22, 2017 at 15:12
• There are only finitely many permutations, hence a maximum exists. If an arrangement does not have parallel order, then you can find a larger value. What more do you think is needed? Commented Jul 22, 2017 at 15:20
• We don't need to find a sum bigger than $S_2.$ We just need to show that every other sum $S_2$ is greater or equal to $S_1$.... Also we do not need to assume strict inequality anywhere. Replace every "$<$" with "$\leq$".... And (although this may be a typo) it should say "$a_r\geq a_s\land b_s\geq b_r$ when $r>s$." Commented Jul 22, 2017 at 19:34

We can prove it by induction.

For $n=2$ we need to prove that $$a_1b_2+a_2b_1\leq a_1b_1+a_2b_2$$ or $$(a_1-a_2)(b_1-b_2)\geq0,$$ which is obvious.

Let $\sum\limits_{i=1}^na_ib_{\sigma(i)}\leq\sum\limits_{i=1}^na_ib_i$ for all $a_1\leq a_2\leq...\leq a_n$, $b_1\leq b_2\leq...\leq b_n$ for all $n\geq2$ and $\sigma\in S_n$.

Now, let $a_1\leq a_2\leq...\leq a_n\leq a_{n+1}$, $b_1\leq b_2\leq...\leq b_n\leq b_{n+1}$ and $\sigma\in S_{n+1}$.

We'll prove that $$\sum_{i=1}^{n+1}a_ib_{\sigma(i)}\leq\sum_{i=1}^{n+1}a_ib_i.$$ If $\sigma(n+1)=n+1$ then by the induction assumption we are done.

Let $\sigma(n+1)=j$ and $\sigma^{-1}(n+1)=k$, where $j\neq n+1$.

Thus, $$a_1b_{\sigma(1)}+...+a_kb_{n+1}+...+a_{n+1}b_j\leq a_1b_{\sigma(i)}+...+a_kb_j+...+a_{n+1}b_{n+1}\leq\sum_{i=1}^{n+1}a_ib_{\sigma(i)}$$ and we are done!