Solutions to two algebra problems for RMO practice

Problem 1.

If a, b, c are non-negative real numbers such that (1+a)(1+b)(1+c)=8, then prove that the product abc cannot exceed 1.

Solution I:

Given that a \geq 0, b \geq 0, c \geq 0, so certainly abc>0, ab>0, bc>0, and ac>0.

Now, (1+a)(1+b) = 1 + a + b + ab and hence, (1+a)(1+b)(1+c) = (1+a+b+ab)(1+c)= 1+a+b+ab+c +ac + bc + abc=8, hence we get:

a+b+c+ab+bc+ca+abc=7.ย Clearly, the presence ofย a+b+c and abc reminds us of the AM-GM inequality.

Here it is AM \geq GM.

So, \frac{a+b+c}{3} \geq (abc)^{1/3}.

Also, we can say: \frac{ab+bc+ca}{3} \geq (ab.bc.ca)^{1/3}. Now, let x=(abc)^{1/3}.

So, 8 \geq 1+3x+3x^{2}+x^{3}

that is, 8 \geq (1+x)^{3}, or 2 \geq 1+x, that is, x \leq 1.ย So, this is a beautiful application of arithmetic mean-geometric mean inequality twice. ๐Ÿ™‚ ๐Ÿ™‚

Problem 2:

If a, b, c are three rational numbers, then prove that :\frac{1}{(a-b)^{2}} + \frac{1}{(b-c)^{2}} + \frac{1}{(c-a)^{2}} is always the square of a rational number.

Solution 2:

Let x=\frac{1}{a-b}, y=\frac{1}{b-c}, z=\frac{1}{c-a}. It can be very easily shown that \frac{1}{x}+ \frac{1}{y} + \frac{1}{z} =0, or xy+yz+zx=0. So, the given expression x^{2}+y^{2}+z^{2}=(x+y+z)^{2} is a perfect square !!!ย BINGO! ๐Ÿ™‚ ๐Ÿ™‚ ๐Ÿ™‚

Nalin Pithwa.

Inequalities and mathematical induction: RMO sample problems-solutions

Problem:

1. Prove the inequality —- 2^{n}(n!)^{2} \leq (2n)! for all natural numbers greater than or equal to 1.

Proof 1:

First consider the following: 2.6. 10.14 \ldots (4n-2)=\frac{(2n)!}{n!}. Let us prove this claim first and then use it to prove what is asked: Towards, that end, consider

RHS = \frac{(2n)(2n-1)(2n-2)(2n-3)(2n-4)\ldots 4.2.1}{1.2.3.4\ldots (n-1)n}=LHS, cancelling off the common factors in numerator and denominator of RHS. (note this can also be proved by mathematical induction! ๐Ÿ™‚ )

In the given inequality:

we need to prove 2^{n}(n!)^{2} \leq (2n)!

consider 2.6.10.14. \ldots (4n-2)=\frac{(2n)!}{n!} where

LHS = (2.1)(2.3) (2.5) (2.7) \ldots 2(n-1), this is an AP with first term 2 and nth term (4n-2) and common difference 4; there are n factors “2”; hence, we 2^{n}1.3.5.7 \ldots (n-1)=\frac{(2n)!}{n!} so we get

2^{n} (n!) 1.3.5.7.\ldots (n-1) = (2n)!; multiplying and dividing RHS of this by 2.4.6.8.\ldots n, we get the desired inequality. Remember the inequality is less than or equal to.

Problem 2:

Establish the Bernoulli inequality: If (1+a) > 0, then (1+a)^{n} \geq 1+na.

Solution 2:

Apply the binomial theorem, which in turn, is proved by mathematical induction ! ๐Ÿ™‚

Problem 3:

For all natural numbers greater than or equal to 1, prove the following by mathematical induction:

\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{n^{2}} \leq 2-\frac{1}{n}

Proof 3:

Let the given proposition be P(n).

Step 1: Check if P(1) is true. Towards that end:

LHS=\frac{1}{1^{2}}=1 and $latex RHS=2-\frac{1}{1}=2-1=1$ and hence, P(1) is true.

Step 2: Let P(n) be true for some n=k, k \in N. That is, the following is true:

\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{k^{2}} \leq 2 -\frac{1}{k}

Add \frac{1}{(k+1)^{2}} to both sides of above inequality, we get the following:

\frac{1}{1^{2}} + \frac{1}{2^{2}} + \frac{1}{3^{2}} + \ldots + \frac{1}{k^{2}} + \frac{1}{(k+1)^{2}} \leq 2-\frac{1}{k}+\frac{1}{(k+1)^{2}}

Now, the RHS in above is 2-\frac{1}{k} +\frac{1}{(k+1)^{2}}=2-\frac{k^{2}+k+1}{k(k+1)^{2}}. We want this to be less than or equal to 2-\frac{1}{k+1}. Now, k \in N, k>1, so what we have to prove is the following:

-\frac{k^{2}+k+1}{k(k+1)^{2}} \leq -\frac{1}{k+1}, that is, we want to prove that

(k+1)(k^{2}+k+1) \geq k(k^{2}+2k+1), that is, we want k^{3}+k^{2}+k+k^{2}+k+1 \geq k^{3}+2k^{2}+k, that is, we want k+1 \geq 0, which is obviously true. QED.

Cheers,

Nalin Pithwa.

An easy inequality from Nordic mathematical contests !?

Reference: Nordic Mathematical Contest, 1987-2009, R. Todev.

Question:

Let a, b, and c be real numbers different from 0ย  and a \geq b \geq c. Prove that inequality

\frac{a^{3}-c^{3}}{3} \geq abc(\frac{a-b}{c} + \frac{b-c}{a})

holds. When does the equality hold?

Proof:

We know that a, b and c are real, distinct and also non-zero and also that a \geq b \geq c.

Hence, c-b \leq 0 \leq a-b, we have (a-b)^{3}\geq (c-b)^{3}, or

a^{3}-3a^{a}b+3ab^{2}-b^{3} \geq c^{3}-3bc^{2}+3b^{2}c-b^{3}

On simplifying this, we immediately have

\frac{1}{3}{(a^{3}-c^{3})} \geq a^{2}b-ab^{2}+b^{2}c-bc^{2}=abc(\frac{a-b}{c}+\frac{b-c}{a}).

A sufficient condition for equality is a=c. If a>c, then (a-b)^{3}>(c-b)^{3}. which makes the proved inequality a strict one. So, a=c is a necessary condition for equality too.

-Nalin Pithwa.

There are many “inequalities” ! :-( :-) !

Reference: R. Todev, Nordic Mathematical Contests, 1987-2009.

Question:

Let a, b, and c be positive real numbers. Prove that \frac{a}{b} + \frac{b}{c} + \frac{c}{a} \leq \frac{a^{2}}{b^{2}} + \frac{b^{2}}{c^{2}} + \frac{c^{2}}{a^{2}}.

Solution:

The arithmetic-geometric inequality yields

3=3\sqrt[3]{\frac{a^{2}}{b^{2}}.\frac{b^{2}}{c^{2}}.\frac{c^{2}}{a^{2}}}\leq \frac{a^{2}}{b^{2}}+\frac{b^{2}}{c^{2}}+\frac{c^{2}}{a^{2}},

or \sqrt{3} \leq \sqrt{\frac{a^{2}}{b^{2}} + \frac{b^{2}}{c^{2}} + \frac{c^{2}}{a^{2}}}…call this relation I.

On the other hand, the Cauchy-Schwarz inequality implies

\frac{a}{b} + \frac{b}{c} + \frac{c}{a} \leq \sqrt{1^{2}+1^{2}+1^{2}}\sqrt{\frac{a^{2}}{b^{2}}+\frac{b^{2}}{c^{2}}+\frac{c^{2}}{a^{2}}}=\sqrt{3}\sqrt{\frac{a^{2}}{b^{2}}+\frac{b^{2}}{c^{2}}+\frac{c^{2}}{a^{2}}}….call this relation II.

We arrive at the inequality we desire by combining relations I and II. Hence, the proof. QED.

Cheers,

Nalin Pithwa.

A “primer” on geometric inequalities for pre-RMO and RMO

The comparison of lengths is more basic than comparison of other geometric quantities (such as angles, areas and volumes). A geometric inequality that involves only the lengths is called a distance inequality.

Some simple axioms and theorems on inequalities in Euclidean geometry are usually the starting point to solve the problem of distance inequality, in which most frequently used tools are:

Proposition I:

The shortest line connecting point A with point B is the segment AB.

The direct corollary of proposition 1 is as follows:

Proposition 2:

(Triangle inequality)

For arbitrary three points A, B and C (lying in the same plane), we have AB \leq AC +CB, the equality holds iff the three points are collinear.

Remark:

In most literature, any symbol of a geometric object also denotes its quantity according to the context.

Proposition 3:

In a triangle, the longer side has the larger opposite angle. And, conversely, the longer angle has the longer opposite side.

Proposition 4:

The median of a triangle on a side is shorter than the half-sum of the other two sides.

Proposition 5:

If a convex polygon is within another one, then the outside convex polygon’s perimeter is larger.

Proposition 6:

Any segment in a convex polygon is either less than the longest side or the longest diagonal of the convex polygon.

Here, is a classic example:

Example 1:

Let a, b, c be the sides of a \triangle ABC. Prove that \frac{a}{b+c} + \frac{b}{c+a} + \frac{c}{a+b}<2.

Solution 1:

By the triangle inequality, a<b+c yields \frac{a}{b+c} = \frac{2a}{2(b+c)} < \frac{2a}{a+b+c}

Similarly, \frac{b}{c+a} < \frac{2b}{a+b+c} and \frac{c}{b+a} < \frac{2c}{a+b+c}

Adding up the above three inequalities, we get the required inequality.

Example 2:

Let AB be the longest side of \triangle ABC, and P a point in the triangle, prove that PA+PB>PC.

Solution/Proof 2:

Let D be the intersection point of CP and AB. (Note P is in the interior of the triangle ABC). Then, \angle ADC or \angle BDC is not acute. Without loss of generality, we assume that \angle ADC is not acute. Applying proposition 3 to \triangle ADC, we obtain AC \geq CD. Therefore, AB \geq AC \geq CD > PC….call this asย  relationship “a”.

Furthermore, applying triangle inequality to \triangle PAB, we have PA+PB>AB…call this as relationship “b”.

Combining “a” and “b”, we obtain the required inequality immediately. QED.

Remarks: (1) If AB is not the longest, then the conclusion may not be true. (2) If point P on the plane of regular triangle ABC, P is not on the circumcircle of the triangle, then the sum of any two of PA, PB, and PC is longer than the remaining one. That is, PA, PB and PC consist of a triangle’s three sides.

Quiz:

Prove that a closed polygonal line with perimeter 1 can be put inside a circle with radius 0.25.

Reference:

Geometric Inequalities, Vol 12, Gangsong Leng, translated by Yongming Liu.

Amazon India link:

Cheers,

Nalin Pithwa.

An inequality for harmonic numbers — RMO Inequalities — Basics

The Harmonic Numbers H_{j} for j=1,2,3, \ldots are defined by

H_{j}=1+\frac{1}{2}+\frac{1}{3} +\ldots +ย  \frac{1}{j}

For instance, H_{4}=1+\frac{1}{2}+\frac{1}{3} + \frac{1}{4} = \frac{25}{12}

Use mathematical induction to show that H_{2^{n}} \geq 1 + \frac{n}{2} whenever n is a non-negative integer.

Solution:

To carry out the proof, let P(n) be the proposition that H_{2^{n}}=1+\frac{n}{2}

Basis step:

P(0) is true because H_{2^{0}}=H_{1}=1 \geq 1 + \frac{0}{2}

Inductive Step:

The inductive hypothesis is the statement that P(k) is true, that is, H_{2^{k}} \geq 1 + \frac{k}{2}

where k is a non-negative integer. We must show that if P(k) is true, then P(k+1), which states that

H_{2^{k+1}} \geq 1 + \frac{k+1}{2}, is also true. So, assuming the inductive hypothesis, it follows that

H_{2^{k+1}} = 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^{k}} + \frac {1}{2^{k}+1} + \ldots + \frac{1}{2^{k+1}}…this step follows from the definition of harmonic number

=H_{2^{k}} + \frac{1}{2^{k}+1} + \ldots + \frac{1}{2^{k+1}}….this step again follows by the definition of 2^{k}th harmonic number

\geq (1+\frac{k}{2}) + \frac{1}{2^{k}+1} + \ldots + \frac{1}{2^{k+1}}…this step follows by the inductive hypothesis

\geq (1+ \frac{k}{2}) + 2^{k}. \frac{2}{2^{k+1}}…because there are 2^{k} terms each greater than or equal to \frac{1}{2^{k+1}}

\geq (1+\frac{k}{2})+ \frac{1}{2}….canceling a common factor of 2^{k} in second term

= 1 + \frac{k+1}{2}

This establishes the inductive step of the proof.

We have completed the basis step and the inductive step. Thus, by mathematical induction P(n) is true for all non-negative integers. That is, the inequality H_{2^{n}} \geq 1 + \frac{n}{2} for the harmonic numbers is valid for all non-negative integers n. QED.

Remark:

The inequality established here shows that the harmonic series 1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} + \ldots is a divergent series. This is an important example in the study of infinite series.

Note:

Google, or through some other literature, find out why harmonic numbers are termed so. You will understand something more beautiful, more deeper !!

Nalin Pithwa.

Uses of mathematical induction to prove inequalities

Some classic examples are presented below to illustrate the use of mathematical induction to prove inequalities:

Example 1:

Prove the inequality n<2^{n} for all positive integers n.

Proof 1:

Let P(n) be the proposition that n<2^{n}.

Basis step:

P(1) is true, because 1<2^{1}=2. This completes the basis step.

Inductive step:

We first assume the inductive hypothesis that P(k) is true for the positive integer k. That is, the inductive hypothesis P(k) is the statement that k<2^{k}. To complete the inductive step, we need to show that if P(k) is true, then P(k+1), which is the statement that k+1<2^{k+1} is also true. That is, we need to show that if k<2^{k}, then k+1<2^{k+1}. To show that this conditional statement is true for the positive integer k, we first add 1 to both sides of k<2^{k} and then note that 1\leq 2^{k}. This tells us that

k+1<2^{k}+1 \leq 2^{k} + 2^{k} = 2.2^{k}=2^{k+1}.

This shows that P(k+1) is true; namely, that k+1<2^{k+1}, based on the assumption that P(k) is true. The induction step is complete.

Therefore, because we have completed both the basis step and the inductive step, by the principle of mathematical induction we have shown that n<2^{n} is true for all positive integers n. QED.

Example 2:

Prove that 2^{n}<n! for every positive integer n with n \geq 4. (Note that this inequality is false for n=1, 2, 3).

Proof 2:

Let P(n) be the proposition that 2^{n}<n!

Basis Step:

To prove the inequality for n \geq 4 requires that the basis step be P(4). Note that P(4) is true because 2^{4} =16<24=4!.

Inductive Step:

For the inductive step, we assume that P(k) is true for the positive integer k with k \geq 4. That is, we assume that 2^{k}<k! with k \geq 4. We must show that under this hypothesis, P(k+1) is also also true. That is, we must show that if 2^{k}<k! for the positive integer k \geq 4, then 2^{k+1}<(k+1)!. We have

2^{k+1}=2.2^{k} (by definition of exposition)

which <2.k! (by the inductive hypothesis)

which <(k+1).k! because 2<k+1

which equals (k+1)! (by definition of factorial function).

This shows that P(k+1) is true when P(k) is true. This completes the inductive step of the proof.

We have completed the basis step and the inductive step. Hence, by mathematical induction P(k) is true for all integers n with n \geq 4. That is, we have proved that 2^{n}<n! is true for all integers n with n \geq 4. QED.

An important inequality for the sum of the reciprocals of a set of positive integers will be proved in the example below:

Example 3:

An inequality for Harmonic Numbers

The harmonic numbers H_{j}, j=1,2,3, \ldots are defined by H_{j}=1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{j}.

For instance, H_{4}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}=\frac{25}{12}. Use mathematical induction to show that H_{2*{n}} \geq 1 + \frac{n}{2}, whenever n is a nonnegative integer.

Proof 3:

To carry out the proof, let P(n) be the proposition that H_{2^{n}} \geq 1 + \frac{n}{2}.

Basis Step:

P(0) is true because H_{2^{0}}=H_{1}=1 \geq 1 + \frac{0}{2}.

Inductive Step:

The inductive hypothesis is the statement that P(1) is true, that is, H_{2^{k}} \geq 1+\frac{k}{2}, where k is a nonnegative integer. We must show that if P(k) is true, then P(k+1), which states that H_{2^{k+1}} \geq 1 + \frac{k+1}{2}, is also true. So, assuming the inductive hypothesis, it follows that

H_{2^{k+1}}=1+\frac{1}{2}+\frac{1}{3}+\ldots +\frac{1}{2^{k}}+\frac{1}{2^{k}+1}+\ldots + \frac{1}{2^{k+1}} (by the definition of harmonic number)

which equals H_{2^{n}}+\frac{1}{2^{k}+1} + \ldots + \frac{1}{2^{k+1}} (by the definition of the 2^{k}th harmonic number)

\geq (1+\frac{k}{2})+\frac{1}{2^{k}+1}+\ldots + \frac{1}{2^{k+1}} (by the inductive hypothesis)

\geq (1+\frac{k}{2}) + 2^{k}\frac{1}{2^{k+1}} (because there are 2^{k} terms each greater than or equal to \frac{1}{2^{k+1}})

\geq (1+\frac{k}{2})+\frac{1}{2} (canceling a common factor of 2^{k} in second term), which in turn, equals 1+ \frac{k+1}{2}.

This establishes the inductive step of the proof.

We have completed the basis step and the inductive step. Thus, by mathematical induction P(n) is true for all nonnegative integers. That is, the inequality H_{2^{n}} \geq 1 + \frac{n}{2} for the harmonic number is valid for all non-negative integers n. QED.

Remark:

The inequality established here shows that theย harmonic series 1+\frac{1}{2}+\frac{1}{3}+\ldots \frac{1}{n}+\ldots is a divergent infinite series. This is an important example in the study of infinite series.

More later,

Nalin Pithwa

Reference: Discrete Mathematics and its Applications by Kenneth H. Rosen, Seventh Edition.