The Art and Craft of Problem Solving

186 CHAPTER 5 ALGEBRA

which equals

(a -b) (x -y) + (a -c) (x -z) + (b -c) (y -z),

and this is positive. If you ponder this argument, you will realize that it generalizes to

any value of n.

Chebyshev's inequality is much less popular than either AM-GM or Cauchy­

Schwarz, but it deserves a place on your toolbelt. In particular, the argument that

we used to prove it can be adapted to many other situations.

Problems and Exercises

5.5.24 Show that

I I I

1+ - + - + - + ... < (^3).
1! 2! 3!
(You have probably learned in a calculus course that
this sum is equal to e ::::: 2.718. But that's cheating!
Use "low-tech" methods.)
5.5.25 Reread the argument about the monotonicity of
the function in Example 5.5.10 on page 175. How does
this relate to the symmetry-product principle?
5.5.26 Rediscover Cauchy's ingenious proof of the
AM-GM inequality for n variables with the following
hints.
(a) First use induction to prove that AM-GM is true
as long as the number of variables is a power of
2.
(b) Next, suppose that you know that AM-GM was
true for four variables, and you want to prove
that it was true for three variables. In other
words, you wish to prove that
x + y + Z > ,r;:;;;;

3

• _yxyz (12)

for all positive x, y, z, and you are allowed to use

the fact that

a+b+c+d >

\!abcd

4 -

(13)

for all positive a, b, c, d. Can you think of some

clever things to substitute for a, b, c, d in (13)

that will transform it into (12)?

(c) Generalize this method to devise a way to go

backward from the 2' -variable AM-GM case

down to AM-GM with any smaller number of

variables (down to 2 r-I).

5.5.27 For which integer n is lin closest to

VI,OOO, OOO -y'999,999?

No calculators, please!

( + I)

n

5.5.28 Prove that n! < T ,forn=2,3,4, ....

5.5.29 (IMO 1976) Determine, with proof, the largest

number that is the product of positive integers whose

sum is 1976. Hint: try an "algorithmic" approach.

5.5.30 Example 3.1.12 on page 71 demonstrated the

factorization

a^3 + b^3 + c^3 - 3abc =

(a +b+ c)(a^2 + b^2 +c^2 -ab - bc -ac).

Use this to prove the AM-GM inequality for three vari­

ables. Does this method generalize?

5.5.31 Show that

_I « �) (�) ... (2n-I)<_I.

J4rl - 2 4 2n ffn

5.5.32 Let aI, a 2 , ... , an be a sequence of positive

numbers. Show that for all positive x,

( al +a 2 +" '+an)

n

(x+at}(x+a 2 )'" (x+an) � x+

n

5.5.33 Find all ordered pairs of positive real numbers

(x,y) such that xY = y. Notice that the set of pairs of

the form (t,t) where t is any positive number is not the

full solution, since 24 = 42 •

5.5.34 Show that

vai+bi+�+"'+�^2

V(al +a 2 +···+an)^2 +(bl +b 2 +···+bn)^2

for all real values of the variables, and give a condition

for equality to hold. Algebraic methods will certainly

work, but there must be a better way ...