Advanced book on Mathematics Olympiad

1.2 Mathematical Induction 9

27.Show that for alln>3 there exists ann-gon whose sides are not all equal and such

that the sum of the distances from any interior point to each of the sides is constant.

(Ann-gon is a polygon withnsides.)

28.The vertices of a convex polygon are colored by at least three colors such that no two

consecutive vertices have the same color. Prove that one can dissect the polygon

into triangles by diagonals that do not cross and whose endpoints have different

colors.

29.Prove that any polygon (convex or not) can be dissected into triangles by interior

diagonals.

30.Prove that any positive integer can be represented as± 12 ± 22 ±···±n^2 for some

positive integernand some choice of the signs.

Now we demonstrate a less frequently encountered form of induction that can be

traced back to Cauchy’s work, where it was used to prove the arithmetic mean–geometric

mean inequality. We apply this method to solve a problem from D. Bu ̧sneag, I. Maftei,

Themes for Mathematics Circles and Contests(Scrisul Românesc, Craiova, 1983).

Example.Leta 1 ,a 2 ,...,anbe real numbers greater than 1. Prove the inequality

∑n

i= 1

1

1 +ai

≥

n

1 +n

√

a 1 a 2 ···an

.

Solution.As always, we start with the base case:

1

1 +a 1

+

1

1 +a 2

≥

2

1 +

√

a 1 a 2

.

Multiplying out the denominators yields the equivalent inequality

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

√

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

After multiplications and cancellations, we obtain

2

√

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

√

a 1 a 2 ≥a 1 +a 2 + 2 a 1 a 2.

This can be rewritten as

2

√

a 1 a 2 ( 1 −

√

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

√

a 1 a 2 − 1 )≥ 0 ,

or

(

√

a 1 a 2 − 1 )(a 1 +a 2 − 2

√

a 1 a 2 )≥ 0.