Solution to puzzle 114: Sums of squares and cubes
Let a, b, and c be positive real numbers such that abc = 1. Show that a2 + b2 + c2 
a3 + b3 + c3.
The Rearrangement Inequality
The rearrangement inequality, stated without proof below, is intuitively quite clear.
Let a1 a2 ... an and b1 b2 ... bn be real numbers. For any permutation (r1, r2, ..., rn) of (b1, b2, ..., bn), we have:
a1b1 + a2b2 + ... + anbn 
a1r1 + a2r2 + ... + anrn a1bn + a2bn−1 + ... + anb1,
with equality if, and only if, (r1, r2, ..., rn) is equal to (b1, b2, ..., bn) or (bn, bn−1, ..., b1), respectively.
That is, the sum is maximal when the two sequences, {ai} and {bi}, are sorted in the same way, and is minimal when they are sorted oppositely.
We will use an extension of the rearrangement inequality to three sequences. This extension has three qualifications:
- The terms of the sequences must be non-negative. (Consider the counterexample a1 = b1 = c1 = −1, a2 = b2 = c2 = 0.)
- There is no equivalent of the minimal sum. (Three sequences cannot all be sorted oppositely.)
- The condition for equality is no longer simply the identity permutation. Indeed, the condition varies with the two permutations.
So the statement of the extension is as given below. Although the extension may be regarded as a standard result, a proof is also given.
Let 0 a1 a2 ... an, 0 b1 b2 ... bn, and 0 c1 c2 ... cn be real numbers.
For any permutations (r1, r2, ..., rn) of (b1, b2, ..., bn), and (s1, s2, ..., sn) of (c1, c2, ..., cn), we have:
a1b1c1 + a2b2c2 + ... + anbncn a1r1s1 + a2r2s2 + ... + anrnsn.
That is, the sum is maximal when the three sequences, {ai}, {bi}, and {ci} are sorted in the same way.
Proof
The proof will be by mathematical induction on n. The result is trivially true for n = 1.
For the induction step, we show that if the result is true for some arbitrary value, n = k − 1, then it also holds for n = k. (Where k > 0.)
Suppose the largest terms in each sequence, ak, bk, and ck are not together in the same product.
Suppose also that ak and bk are found in the terms akbpcq + arbkcs.(1)
Suppose, without loss of generality, that cq cs. Then the terms of the b sequence and the c sequence are increasing, but those of the a sequence are decreasing.
If we write (1) as ak(bpcq) + ar(bkcs), and consider the bracketed terms as single terms, then, since all terms are non-negative, we have bpcq bkcs, and we can apply the rearrangement inequality for two sequences.
Hence arbpcq + akbkcs akbpcq + arbkcs.
Using this technique, we may bring together (if they are apart) the terms ak, bk, and ck in one product, without diminishing the sum. The technique also shows that no larger sum may be formed with ak, bk, and ck not together in the same product. Hence the largest sum must occur when ak, bk, and ck are together. (Since the sorting process is finite, it converges, and the maximum is actually found.)
Hence, by the inductive hypothesis, the result is true for k. This concludes the proof by induction.
abc = 1 implies a2 + b2 + c2 
a3 + b3 + c3
Now consider a2 + b2 + c2 a3 + b3 + c3.
We homogenize the inequality by incorporating the side condition, that is, by multiplying the left-hand side by 1 = (abc)1/3, yielding the candidate inequality below, in which all terms are now of degree 3.
a7/3b1/3c1/3 + a1/3b7/3c1/3 + a1/3b1/3c7/3 a3 + b3 + c3.(1)
If we can prove this inequality, then the target inequality will follow upon division by 1 = (abc)1/3.
Assume without loss of generality that a b c.
Then the sequences
{a7/3, b7/3, c7/3},
{a1/3, b1/3, c1/3},
{a1/3, b1/3, c1/3},
are sorted in the same way, while the sequences
{a7/3, b7/3, c7/3},
{b1/3, c1/3, a1/3},
{c1/3, a1/3, b1/3},
are not sorted the same way.
Applying the rearrangement inequality for three sequences to the above sequences, we obtain (1).
We then divide the left-hand side of (1) by 1 = (abc)1/3, obtaining
a2 + b2 + c2 a3 + b3 + c3.
Therefore, if abc = 1, we conclude a2 + b2 + c2 a3 + b3 + c3.
Remarks
Clearly the above proof may be generalized to show that, if abc = 1, then, for any positive integer n:
3 a + b + c a2 + b2 + c2 a3 + b3 + c3 a4 + b4 + c4 ... an + bn + cn.
Inequality (1) may also be proved using Muirhead's Inequality.
A simpler solution
Greg Muller sent the following ingenious solution.
Lemma
For R a positive real number and n a positive integer, Rn(R − 1) (R − 1), with equality if and only if R = 1.
Proof
Consider the three cases, R > 1, R = 1, R < 1, all of which are straightforward.
- Case R > 1: Rn > 1 and R − 1 > 0
Rn(R − 1) > (R − 1). - Case R = 1: R − 1 = 0 Rn(R − 1) = (R − 1).
- Case R < 1: 0 < Rn < 1 and R − 1 < 0 (R − 1) < Rn(R − 1) < 0.
We must now show that abc = 1 a2 + b2 + c2 a3 + b3 + c3.
This is equivalent to showing that a3 + b3 + c3 − a2 − b2 − c2 0.
But a3 + b3 + c3 − a2 − b2 − c2 = a2(a − 1) + b2(b − 1) + c2(c − 1) (a − 1) + (b − 1) + (c − 1) = (a + b + c) − 3.
By the Arithmetic Mean-Geometric Mean Inequality, (a + b + c)/3 (abc)1/3 = 1.
Hence a + b + c 3.
Therefore, a3 + b3 + c3 − a2 − b2 − c2 0, and the result follows.
Additional problem
Let a, b, and c be positive real numbers such that a + b + c = 1. Show that a2 + b2 + c2 3(a3 + b3 + c3).
Further reading
The Rearrangement Inequality by K. Wu and Andy Liu -- a tutorial that shows how to derive many other inequalities, such as Arithmetic Mean - Geometric Mean, Geometric Mean - Harmonic Mean, and Cauchy-Schwartz, from the Rearrangement Inequality
Source: The Cauchy-Schwarz Master Class, by J. Michael Steele. See Chapter 12. With special thanks to Andy Liu for help in proving the rearrangement inequality for three sequences.