The Art and Craft of Problem Solving

5.5 INEQUALITIES 181

Thus the n^2 terms can be decomposed into n terms that equal 1 and (n^2 - n) /2

pairs of terms, with each pair greater than or equal to 2. Consequently, the entire sum

is greater than or equal to

n^2 - n 2

n.l +-

2

- ·2=n.

Massage, Cauchy-Schwarz, and Chebyshev

There are many, many kinds of inequalities, with literally hundreds of different the­
orems and specialized techniques. We will briefly look at three important "interme­
diate" ideas: more about massage, the Cauchy-Schwarz inequality, and Chebyshev's
inequality.
Perhaps the most important inequality tactic is massage, which we encountered
earlier (for example, the discussion of harmonic series in Example 5.3. 4 on page 161).

The philosophy of massage is to "loosen up" an expression in such a way that it even­

tually becomes easier to deal with. This is not restricted to inequalities, of course.
Sometimes the first stage of massage seemingly worsens the difficulty. But that is
temporary, much like physical massage, which can be rather painful until your mus­
cles magically relax. Here is an instructive example that combines massage with its
frequent partner, telescoping.

(^10000 1)
Example 5.5. 19 Let A = � r.;.. Find l A J without a calculator.
n=^1 yn
Solution: In other words, we must estimate A to the nearest integer. We don't
need an exact value, so we can massage the terms, perturbing them a bit, so that they
telescope. We have

12 2

- = -< =2(Vn -vn=t)

Vn 2 Vn Vn + vn=t

'

where we rationalized the denominator in the last step. Likewise,

In other words,

1 2

r.;. > v'n+T Vn = 2( v'n+T - Vn).

yn n+l+ n

1

2( v'n+T - Vn) < Vn < 2( Vn -vn=t).

That was the crux move, for we have bounded the term 1/ Vn above and below by
terms that will telescope when summed. Indeed, we have

10000

� 2( v'n+T -Vn) = 2v'IOOOI - 2

n= 1

and

10000

� 2( Vn -vn=t) = 2 JlOOOO -v'O.

n= 1