Advanced book on Mathematics Olympiad

Methods of Proof 345

a+b+c> 4 d. Let us look at the situation in whichdisa 3 anda, b, andcarea 1 ,a 2 ,

anda 4. The inequalitya 1 +a 2 +a 4 < 4 +a 3 is impossible becausea 4 ≥a 3 +1 and

a 1 +a 2 ≥3. Thus with our assumption,a 1 +a 2 +a 4 > 4 a 3 ,or

a 4 > 4 a 3 −a 2 −a 1.

By similar logic,

a 5 > 4 a 4 −a 2 −a 1 > 16 a 3 − 5 a 2 − 5 a 1 ,

a 6 > 4 a 5 −a 2 −a 1 > 64 a 3 − 21 a 2 − 21 a 1 ,

a 7 > 4 a 6 −a 2 −a 1 > 256 a 3 − 85 a 2 − 85 a 1 ,

a 8 > 4 a 7 −a 2 −a 1 > 1024 a 3 − 341 a 2 − 341 a 1.

We want to show that if this is the case, thena 8 should exceed 2004. The expression

1024 a 3 − 341 a 2 − 341 a 1 can be written as 683a 3 + 341 (a 3 −a 2 )+ 341 (a 3 −a 1 ),so

to minimize it we have to choosea 1 =1,a 2 =2,a 3 =3. But then the value of the

expression would be 2049, which, as predicted, exceeds 2004. This contradiction shows

that our assumption was false, proving the existence of the desired four numbers.

(Mathematical Olympiad Summer Program, 2004, proposed by T. Andreescu)

56.There is no loss of generality in supposing thata 1 <a 2 <···<an<···.Now

proceed by induction onn. Forn=1,a 12 ≥^2 ×^13 +^1 a 1 follows froma 1 ≥1. The inductive

step reduces to

an^2 + 1 ≥

2

3

(a 1 +a 2 +···+an)+

2 n+ 3

3

an+ 1.

An equivalent form of this is

3 an^2 + 1 −( 2 n+ 3 )an+ 1 ≥ 2 (a 1 +a 2 +···+an).

At this point there is an interplay between the indices and the terms of the sequence,
namely the observation thata 1 +a 2 +···+andoes not exceed the sum of integers from
1toan. Therefore,

2 (a 1 +a 2 +···+an)≤ 2 ( 1 + 2 +···+an)=an(an+ 1 )≤(an+ 1 − 1 )an+ 1.

We are left to prove the sharper, yet easier, inequality

3 a^2 n+ 1 −( 2 n+ 3 )an+ 1 ≥(an+ 1 − 1 )an+ 1.

This is equivalent toan+ 1 ≥n+1, which follows from the fact thatan+ 1 is the largest of

the numbers.

(Romanian Team Selection Test for the International Mathematical Olympiad, pro-

posed by L. Panaitopol)