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.

Heights and Distances — II — problems for RMO and IITJEE maths

This is one of the prime utilities of trigonometry —- to calculate heights and distances, called as surveying in civil engineering.

1. From the extremities of a horizontal base line AB, whose length is 1 km, the bearings of the foot C of a tower are observed and it is found that \angle {CAB} is 56 degrees and 23 minutes and \angle{CBA} is 47 degrees and 15 minutes, and the elevation of the tower from A is 9 degrees and 25 minutes, find the height of the tower.

2. A man in a balloon observes that the angle of depression of an object on the ground bearing due north is 33 degrees; the balloon drifts 3 km due west and the angle of depression is now found to be 21 degrees. Find the height of the balloon.

3. A tower PN stands on level ground. A base AB is measured at right angles to AN, the points A, B, and N being in the same horizontal plane, and the angles PAN and PBN are found to be \alpha and \beta respectively. Prove that the height of the tower is

AB\frac{\sin {\alpha}\sin{\beta}}{\sqrt{\sin{(\alpha-\beta)}\sin{(\alpha+\beta)}}}

If AB is 100m, \alpha = 70 degrees and \beta = 50 degrees, calculate the height.

4. At each end of a horizontal base of length 2a, it is found that the angular height of a certain peak is \theta and that at the middle point it is \phi. Prove that the vertical height of the peak is

\frac{a \sin {\theta}\sin{\phi}}{\sqrt{\sin{(\phi+\theta)}\sin{(\phi-\theta)}}}

5. To find the distance from A to P, a distance AB of 1 km. is measured for a convenient direction. At A the angle PAB is found to be 41 degrees 18 min and at B, the angle PBA is found to be 114 degrees and 38 min. What is the required distance to the nearest metre?

More later,

Nalin Pithwa

Heights and Distances — I — problems for RMO and IITJEE Maths

1. A man observes that at a point due south of a certain tower its angle of elevation is 60 degrees. He then walks 100 meters due west on a horizontal plane and finds that the angle of elevation is 30 degrees. Find the height of the tower and his original distance from it.

2. At the foot of a mountain the elevation of its summit is found to be 45 degrees; after ascending 1000 m towards the mountain up a slope of 30 degree inclination, the elevation is found to be 60 degrees. Find the height of the mountain.

3. A square tower stands upon a horizontal plane, from which three of its upper corners are visible, their angular elevations are respectively 45 degrees, 60 degrees and 45 degrees. Show  that the height of the tower is to the breadth of one of its sides as \sqrt{6}(\sqrt{5}+1) to 4.

4. A lighthouse, facing north, sends out a fan-shaped beam of light extending from north-east to north-west. An observer on a steamer, sailing due west, first sees the light when is 5 km, away from the lighthouse and continues to see it for 30\sqrt{2} minutes. What is the speed of the steamer?

5. A man stands at a point X on the bank XY of a river with straight and parallel banks, and observes that the line joining X to a point Z on the opposite bank makes an angle of 30 degrees with XY. He then goes along the bank a distance of 200 meters to Y and finds that the angle ZYX is 60 degrees. Find the breadth of the river.

6. A man, walking due north, observes that the elevation of a balloon, which is due east of him and is sailing toward the north-west, is then 60 degrees; after he has walked 400 meters the balloon is vertically over his head; find its height supposing it to have always remained the same.

The above are some tricky trig problems ! What is the main trick ? I will suggest a very simple hint: draw as good diagrams as possible!

Nalin Pithwa

Combinatorics for RMO and IITJEE maths

Problem:

How many arrangements of 5 \alpha‘s, 5 \beta‘s and \gamma‘s are there with at least one \beta and at least one \gamma between each successive pair of \alpha‘s?

Solution:

There are three cases:

  1. Exactly one \beta and one \gamma between each pair of \alpha‘s: Between each of the four pairs of \alpha‘s, the \beta or the \gamma can be first — 2^{4} ways. The fifth \beta and fifth \gamma along with the sequence of the rest of the letters can be considered as 3 objects to be arranged — 3! ways. Altogether, 2^{4} \times 3!=96 ways.
  2. Exactly, one \beta between each pair of \alpha‘s and two \gamma‘s between some pair of \alpha‘s (or two \beta‘s between some pair of \alpha‘s and exactly one \gamma between each pair of \alpha‘s): there are four choices for between which pair of \alpha‘s the two \gamma‘s go and 3 ways to arrange the two \gamma‘s and one \beta there. There are two 2^{3} choices for whether the \beta or the \gamma goes first between the other 3 pairs of \alpha‘s and 2 choices for at which end of the arrangement the fifth \beta goes. Multiplying by 2 for the case of two \beta‘s between some pair of \alpha‘s, we obtain 2 \times (4 \times 3 \times 2^{3} \times 2)=384 ways.
  3. Two \beta‘s between some pair of \alpha‘s and two \gamma‘s between some pair of \alpha‘s. There are two subcases. If the two \beta‘s and two \gamma‘s are between the same pair of \alpha‘s, there are 4 choices for which pair of \alpha‘s, C(4,2) ways to arrange them between this pair of \alpha‘s, and 2^{3} choices for whether the \beta or the \gamma goes first between the other 3 pairs of \alpha‘s. If two \beta‘s and two \gamma‘s are between the different pairs of \alpha‘s, there are 4 \times 3 ways to pick between which \alpha‘s  the two \beta‘s and then between which \alpha‘s the two \gamma‘s go, 3^{2} ways to arrange the two \gamma‘s and one \beta and to arrange the one \gamma and two \beta‘s, and 2^{2} choices for whether the \beta or the \gamma goes first between the other 2 pair of \alpha‘s. Together, 4 \times C(4,2) \times 2^{3} + 4 \times 3 \times 3^{2} \times 2^{2}=1056 ways.

All together, the three cases give us a total of 96+384+1056=1536 arrangements.

More later,

Nalin Pithwa

The Pigeon Hole Principle : Practice Problems

Problem 1:

A bag contains beads of two colours: black and white. What is the smallest number of beads which must be drawn from the bag, without looking, so that among these beads, there are two of the same colour?

Problem 2:

One million pine trees grow in a forest. It is known that no pine tree has more than 600000 pine needles on it. Show that two pine trees in the forest must have the same number of pine needles.

Problem 3:

Given twelve integers, show that two of them can be chosen whose difference is divisible by 11.

More later. Kindly send your comments, answers, etc.

Nalin Pithwa

Basic Mathematical Logic I for IITJEE and Math and Physics Olympiads

It is necessary to think clearly and to communicate precisely. Whereas in the arts and other disciplines, there is no room for ambiguity in the mathematical sciences. Here’s a primer on logic for aspirants of IITJEE, and Mathematics and Physics Olympiads.

Reference: 

1) Introduction to General Topology  by K.D. Joshi

2) Topology by Munkres

Mathematics is a language. For example, language of physics. If Math is regarded as a language, then logic is its grammar. In other words, logical precision has the same importance in Math as grammatical correctness in a language.

I. Statements and their Truth Values:

A statement is a declarative sentence, conveying a definite meaning, which may be either true or false but not both simultaneously. Incomplete sentences, questions and exclamations are not statements.

Some examples of statements are:

i) John is intelligent.

ii) If there is life on Mars, then the postman delivers a letter.

iii) Either grandmother chews gum, or missiles are costly.

iv) Every man is mortal.

v) All men are mortal.

vi) There is a man, who is eight feet tall.

vii) Every even integer greater than 2 can be expressed as a sum of 2 prime numbers.

viii) Every man with six legs is intelligent.

Some remarks on the above:

Statements 4 and 5 are statements about all the members of a class. So, in order to produce a counter-example, we say “there exists a man who  is not mortal” or in polished English, “there exists a man who is immortal”. By truth value of a statement, we mean, unambiguously, whether it is true or false (no grey areas here; it’s all black and white!!), Truth value is known to electrical engineers or computer scientists/engineers as digital logic or binary logic. (Actually, math students will recall here boolean laws of thought or set theory).  A conjecture is a statement whose truth value is not known at present. Thus, statement (vii) is the famous Goldbach conjecture. Statement six talks about a six-legged man, and of course, there is no such man (at least on earth!) and hence, we cannot produce a counter example, and hence, the statement is said to be vacuously true. Note also says that statement (ii) sounds strange. This statement is only mathematical “if then” statement; it is not a statement of cause and effect in the physical universe subject to laws of physics/chemistry/biology ! So, also the next statement.

Can the following be valid statements?

  • Will it rain
  • Oh! those heavy rains.
  • I am telling you a lie.

Out of the above, the first two are not statements, obviously. The third statement refers to itself, and hence, is circular, and is called a paradox.

II) Negation, Conjunction, Disjunction and their values:

IIa) Negation: To negate a statement, technically speaking, simply put a NOT in front of the whole statement. The negation of a statement is its counter-example.

Here’s an interesting example: consider the statement, “John is very intelligent”. The negation is not “John is very dull”. The original statement refers to degrees of intelligence. So, the correct negation is “John is not very intelligent”.

Consider the following statement: For every x \in A,, statement P holds. The negation of this statement is as follows: For at least one x \in A, statement P does not hold. Equivalently, there exists some x \in A such that statement P does not hold.

IIb) Disjunction or the meaning of “OR”:

In ordinary, everyday, colloquial English, the word “OR” is ambiguous. Sometimes, the statement “P or Q” means “P or Q or both” and sometimes, it means “P or Q but not both”. (EEs and CS engineers know this as inclusive OR and Exclusive OR). Usually, one decides from the context, which meaning is intended. For example, suppose I spoke two students as follows:

“Mr. Smith, every student registered for this course has taken either a course in linear algebra or a course in analysis.”

“Mr. Jones, either you get a grade of at least 70 on the final exam, or you will flunk this course.”

In the context, Mr. Smith knows perfectly well that I  mean ” everyone has had linear algebra or analysis or both”, and Mr. Jones knows I mean “either he gets at least 70 or he flunks, but not both.” Indeed, Mr. Jones would be exceedingly unhappy if both statements turned out to be true!!

In math, one cannot tolerate such ambiguity. In math, “or” always means “P or Q or both”. If we mean “P or Q or both, but not both”, we have to state it explicitly.

Meaning of “if …then”:

In everyday English, a statement of the form “if…then” is ambiguous. It always means if P is true, then Q is true. Sometimes, that is all it means, other times it means something more; that, if P is false, Q must be false. Usually, one decides from the context which interpretation is correct.

Examples:

“Mr. Smith, if any student registered for this course has not taken a course in linear algebra, then he has taken a course in analysis.”

“Mr. Jones, if you get a grade below 70 on the final, you are going to flunk this course.”

In the context, Mr. Smith understands that if a student in this course has not  had linear algebra, then he has taken analysis, but if he has had linear algebra, he may or may not have taken analysis as well. And, Mr. Jones knows that  if he gets a grade below 70, he will flunk the course, but if he gets a grade of at least 70, he will pass.

In math, if p, then q means the following: if p is true, q is true. But, if p is false, q may be either true or false. 

Contrapositive of a statement:

A statement of the form “if p, then q” is same as “if NOT q, then NOT p”. The latter is called its contrapositive. Many a times, it is easier to prove the contrapositive of a statement rather than the original statement!!

Example: If x < 0, then x^{3} \neq 0.

Contrapositive: if x ^{3}=0, then it is not true that x > 0.

Example: If x^{2}<0, then x=23.

Contrapositive: if x \neq 23, then it is not true that x^{2}<0

Converse of a statement:

The converse of a statement of the form “if p, then q” is “if q, then p”. Note that a statement and its converse are not the same.

Example: If a function is differentiable, then it is continuous. But, the converse is true. (that, if a function is continuous, it is differentiable).

Note: A definition is always if and only if; that is, if p, then q AND if q, then p.