Advanced book on Mathematics Olympiad

336 Methods of Proof

This is clearly the same as

f

(

x 1 +x 2 +···+xn− 1

n− 1

)

=

f(x 1 )+x 2 +···+f(xn− 1 )

n− 1

,

and the argument is complete.

32.This is a stronger form of the inequality discussed in the beginning, which can be
obtained from it by applying the AM–GM inequality.
We first prove that the property holds forna power of 2. The base case

( 1 +a 1 )( 1 +a 2 )≥( 1 +

√

a 1 a 2 )^2

reduces to the obviousa 1 +a 2 ≥ 2

√

a 1 a 2.

If

( 1 +a 1 )( 1 +a 2 )···( 1 +a 2 k)≥

(

1 +^2 k

√

a 1 a 2 ···a 2 k

) 2 k

for every choice of nonnegative numbers, then

( 1 +a 1 )···( 1 +a 2 k+ 1 )=( 1 +a 1 )···( 1 +a 2 k)( 1 +a 2 k+ 1 )···( 1 +a 2 k+ 1 )

≥

(

1 +^2 k

√

a 1 ···a 2 k

) 2 k(

1 +^2 k

√

a 2 k+ 1 ···a 2 k+ 1

) 2 k

≥

[(

1 +

√

2 √ka 1 ···a 2 k 2 √ka 2 k+ 1 ···a 2 k+ 1

) 2 ]^2 k

=

(

1 +^2 k+^1

√

a 1 ···a 2 k+ 1

) 2 k+^1

.

This completes the induction.
Now we work backward. If the inequality holds forn+1 numbers, then choosing
an+ 1 =n

√

a 1 a 2 ···an, we can write

( 1 +a 1 )···( 1 +an)( 1 +n

√

a 1 ···an)≥

(

1 +n+^1

√

a 1 ···ann

√

a 1 ···an

)n+ 1

,

which is the same as

( 1 +a 1 )···( 1 +an)( 1 +n

√

a 1 ···an)≥( 1 +n

√

a 1 ···an)n+^1.

Canceling the common factor, we obtain the inequality fornnumbers. The inequality is
proved.

33.The “pigeons’’ are the numbers. The “holes’’ are the 49 sets

{ 1 , 98 },{ 2 , 97 },...,{ 49 , 50 }.