The rearrangement inequality states that, for two sequences and , the inequalities
hold, where is any permutation of .
Consider a permutation such that is maximized. The desired result is that is the identity permutation: i.e. for all . Suppose for the sake of contradiction that is not the identity, and let be the smallest integer such that .
Since is the smallest such integer, this means that (as the numbers to are already assigned). Furthermore, there must exist a such that , as some number must be assigned to .
Now, since , it follows that . Similarly, since , it follows that . Therefore,
so the sum is not decreased by changing to . This implies that the identity permutation gives the maximum possible value of , as desired.
The value of the rearrangement inequality lies chiefly in the fact that it formalizes one's intuition towards what amounts to a greedy algorithm. For instance, if one were presented with a large number of $20 bills, $10 bills, $5 bills, and $1 bills, with the instructions to take 4 of one type of bill, 3 of another, 2 of another, and 1 of the last, it is intuitively obvious that four $20 bills, three $10 bills, two $5 bills, and one $1 bill should be selected. Indeed, this is precisely the statement of the rearrangement inequality, applied to the sequences and .
Like the Chebyshev inequality, care must be taken to assure both sequences are similarly ordered. Common strategies include
Cycling the variables is also a powerful technique, as this preserves some ordering. For instance,
for reals .
Assume without loss of generality that . By rearrangement,
which is precisely the desired inequality.
A similar strategy leads to another proof of the AM-GM inequality:
for positive reals .
Assume without loss of generality that . The rearrangement inequality tells us that
which implies that
Additionally, the rearrangement inequality tells us that
which implies that
so it suffices to show that , or . This argument is then repeated until it is left to prove that , which is self-evident.