The Art and Craft of Problem Solving

5.5 INEQUALITIES^185

Thus (1 1) reduces to

2S(x+y+z);:::: (x+y+z)^2 ,

which in tum is equivalent to

2S ;:::: (x+y+z).

But by AM-GM, we have

x+y+z;:::: 3�=3,

since xyz = 1. We conclude that 2S ;:::: 3, and we can rest.

Chebyshev's Inequality

Let ai, a 2 , ... ,an and bl ,b 2 , ... ,bn be sequences of real numbers that are monotonic in

the same direction. In other words, we have al � a 2 � ... � an and bl � b 2 � ... � bn

(or we could reverse all the inequalities). Chebyshev's inequality states that

In other words, if you order two sequences, then the average of the products of corre­
sponding elements is at least as big as the product of the averages of the two sequences.
Let us try to prove Chebyshev's inequality, by looking at a few simple cases. If
n = 2, we have (using nicer variables) the alleged inequality

(^2) (ax +by);:::: (a+b)(x+y).
This is equivalent to
ax + by ;:::: ay + bx,
which is equivalent to
(a-b)(x -y);:::: 0,
which is true, since the sequences are ordered (thus a -b and x -y will be the same
sign and their product is non-negative).
If n = 3, we are faced with verifying the truth of
3 (ax +by+ez);:::: (a+b+e)(x+y+z),
where a � b � e and x � y � z. Inspired by the previous case, we subtract the right­
hand side from the left-hand side and do some factoring in order to show that the
difference is positive. When we subtract, three terms cancel and we are left with the
12 terms
�-�+�-m+�-�+�-�+Q-cr+Q-ry
Rearrange these into the sum
(�+by) - (ay +bx) + (ax +ez) - (ax + ex) + (by +ez) - (bz +ey),