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} 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}

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} 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} 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

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} 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.

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.

Real Numbers, Sequences and Series: part 9

Definition.

We call a sequence $(a_{n})_{n=1}^{\infty}$ a Cauchy sequence if for all $\varepsilon >0$ there exists an $n_{0}$ such that $|a_{m}-a_{n}|<\varepsilon$ for all m, $n > n_{0}$.

Theorem:

Every Cauchy sequence is a bounded sequence and is convergent.

Proof.

By definition, for all $\varepsilon >0$ there is an $n_{0}$ such that

$|a_{m}-a_{n}|<\varepsilon$ for all m, $n>n_{0}$.

So, in particular, $|a_{n_{0}}-a_{n}|<\varepsilon$ for all $n > n_{0}$, that is,

$a_{n_{0}+1}-\varepsilon for all $n>n_{0}$.

Let $M=\max \{ a_{1}, \ldots, a_{n_{0}}, a_{n_{0}+1}+\varepsilon\}$ and $m=\min \{ a_{1}, \ldots, a_{n_{0}+1}-\varepsilon\}$.

It is clear that $m \leq a_{n} \leq M$, for all $n \geq 1$.

We now prove that such a sequence is convergent. Let $\overline {\lim} a_{n}=L$ and $\underline{\lim}a_{n}=l$. Since any Cauchy sequence is bounded,

$-\infty < l \leq L < \infty$.

But since $(a_{n})_{n=1}^{\infty}$ is Cauchy, for every $\varepsilon >0$ there is an $n_{0}=n_{0}(\varepsilon)$ such that

$a_{n_{0}+1}-\varepsilon for all $n>n_{0}$.

which implies that $a_{n_{0}+1}-\varepsilon \leq \underline{\lim}a_{n} =l \leq \overline{\lim}a_{n}=L \leq a_{n_{0}+1}+\varepsilon$. Thus, $L-l \leq 2\varepsilon$ for all $\varepsilon>0$. This is possible only if $L=l$.

QED.

Thus, we have established that the Cauchy criterion is both a necessary and sufficient criterion of convergence of a sequence. We state a few more results without proofs (exercises).

Theorem:

For sequences $(a_{n})_{n=1}^{\infty}$ and $(b_{n})_{n=1}^{\infty}$.

(i) If $l \leq a_{n} \leq b_{n}$ and $\lim_{n \rightarrow \infty}b_{n}=l$, then $(a_{n})_{n=1}^{\infty}$ too is convergent and $\lim_{n \rightarrow \infty}a_{n}=l$.

(ii) If $a_{n} \leq b_{n}$, then $\overline{\lim}a_{n} \leq \overline{\lim}b_{n}$, $\underline{\lim}a_{n} \leq \underline{\lim}b_{n}$.

(iii) $\underline{\lim}(a_{n}+b_{n}) \geq \underline{\lim}a_{n}+\underline{\lim}b_{n}$

(iv) $\overline{\lim}(a_{n}+b_{n}) \leq \overline{\lim}{a_{n}}+ \overline{\lim}{b_{n}}$

(v) If $(a_{n})_{n=1}^{\infty}$ and $(b_{n})_{n=1}^{\infty}$ are both convergent, then $(a_{n}+b_{n})_{n=1}^{\infty}$, $(a_{n}-b_{n})_{n=1}^{\infty}$, and $(a_{n}b_{n})_{n=1}^{\infty}$ are convergent and we have $\lim(a_{n} \pm b_{n})=\lim{(a_{n} \pm b_{n})}=\lim{a_{n}} \pm \lim{b_{n}}$, and $\lim{a_{n}b_{n}}=\lim {a_{n}}\leq \lim {b_{n}}$.

(vi) If $(a_{n})_{n=1}^{\infty}$, $(b_{n})_{n=1}^{\infty}$ are convergent and $\lim_{n \rightarrow \infty}b_{n}=l \neq 0$, then $(\frac{a_{n}}{b_{n}})_{n=1}^{\infty}$ is convergent and $\lim_{n \rightarrow \frac{a_{n}}{b_{n}}}= \frac{\lim {a_{n}}}{\lim{b_{n}}}$.

Reference: Understanding Mathematics by Sinha, Karandikar et al. I have used this reference for all the previous articles on series and sequences.

More later,

Nalin Pithwa

High School Geometry: Chapter I: Basic Theorem

If two chords of a circle intersect anywhere. at any angle, what can be said about the segments of each cut off by the other? The data seem to be too for any conclusion, yet an important and far reaching theorem can be formulated from only this meager amount of “given”:

Theorem 2.

If two chords intersect, the product of the segments of the one equals the product of the segments of the other.

This theorem says that in Fig. 3A (attached as a jpeg picture), $PA.PB=PC.PD$ (where the dot is the symbol for algebraic multiplication). What do we mean when we talk about “the product of two line segments”? (There is a way to multiply two lines with a ruler and a compass, but we won’t discuss it here.) What the theorem means is that the product of the respective lengths of the segments are equal. Whenever we put a line segment like PA into an equation, we shall mean the length of PA. (Although we shall soon have to come to grips with the idea of a “negative length” for the present we make no distinction between the length of PA and the length of AP; they are the same positive number).

The Greek geometers took great care to enumerate the different cases of the above theorem. Today, we prefer, when possible, to treat all variants together in one compact theorem. In Fig 3A, the chords intersect inside the circle, in 3B outside the circle, and in 3C one of the chords has become a tangent. Theorem 2 holds in all three cases, and the proofs are so much alike that one proof virtually goes for all.

You may object, and say that in Fig. 3B the chords don’t intersect. But, they do when extended, and in these blogs, we shall say that one line intersects a second when it in fact only intersects the extension of the second line. This is just part of a terminology, in quite general use today, that may be slightly more free-wheeling than what you have been accustomed to. In the same vein, P divided AB internally in Fig 3A, whereas in Fig 3B, P is said to divide the chord AB externally, and we still talk about the two segments PA and PB.

To prove theorem 2, we need to construct two lines, indicated in Fig 3A. Perhaps, you should draw them also in figures 3B and 3C, and, following the proof letter for letter, see for yourself how few changes are required to complete the proofs of these diagrams. In Fig 3A, $\angle {1}= \angle {2}$ because they are inscribed in the same circular arc. And, $\angle {5} = \angle {4}$. Therefore, triangles PCA and PBD are similar, and hence have proportional sides:

$\frac {PA}{PD} = \frac {PC}{PB}$ or $PA. PB = PC.PD$

In the next blog, we will discuss means and another basic theorem.

Till then, aufwiedersehen,

Nalin Pithwa

Real Numbers, Sequences and Series: part 8

Definition. A sequence is a function $f:N \rightarrow \Re$. It is usual to represent the sequence f as $(a_{n})_{n=1}^{\infty}$ where $f(n)=a_{n}$.

Definition. A sequence $(a_{n})_{n=1}^{\infty}$ is said to converge to a if for each $\varepsilon>0$ there is an $n_{0}$ such that

$|a_{n}-a|<\varepsilon$ for all $n > n_{0}$.

It can be shown that this number is unique and we write $\lim_{n \rightarrow \infty}a_{n}=a$.

Examples.

(a) The sequence $\{ 1, 1/2, 1/3, \ldots, 1/n \}$ converges to 0. For $\varepsilon>0$, let $n_{0}=[\frac{1}{\varepsilon}]+1$. This gives

$|\frac{1}{n}-0|=\frac{1}{n}<\varepsilon$ for all $n>n_{0}$.

(b) The sequence $\{ 1, 3/2, 7/4, 15/8, 31/16, \ldots\}$ converges to 2. The nth term of this sequence is $\frac{2^{n}-1}{2^{n-1}}=2-\frac{1}{2^{n-1}}$. So $|2-(2-\frac{1}{2^{n-1}})|=\frac{1}{2^{n-1}}$. But, $2^{n-1} \geq n$ for all $n \geq 1$. Thus, for a given $\varepsilon >0$, the choice of $n_{0}$ given in (a) above will do.

(c) The sequence $(a_{n})_{n=1}^{\infty}$ defined by $a_{n}=n^{\frac{1}{n}}$ converges to 1.

Let $n^{\frac{1}{n}}=1+\delta_{n}$ so that for $n >1$, $\delta_{n}>0$. Now, $n=(1+\delta_{n})^{n}=1+n\delta_{n}+\frac{n(n-1)}{2}(\delta_{n})^{2}+\ldots \geq 1+\frac{n(n-1)}{2}(\delta_{n})^{2}$, thus, for $n-1>0$, we have $\delta_{n} \leq \sqrt{\frac{2}{n}}$. For any $\varepsilon > 0$, we can find $n_{0}$ in N such that $n_{0}\frac{(\varepsilon)^{2}}{2}>1$. Thus, for any $n > n_{0}$, we have $0 \leq \delta_{n} \leq \sqrt{\frac{2}{n}} \leq \sqrt{\frac{2}{n_{0}}}<\varepsilon$. This is the same as writing

$|n^{\frac{1}{n}}-1|<\varepsilon$ for $n > n_{0}$ or equivalently, $\lim_{n \rightarrow \infty}n^{\frac{1}{n}}=1$

(d) Let $a_{n}=\frac{2^{n}}{n!}$. The sequence $(a_{n})_{n=1}^{\infty}$ converges to o. Note that

$a_{n}=\frac{2}{1}\frac{2}{2}\frac{2}{3}\ldots\frac{2}{n}<\frac{4}{n}$ for $n>3$.

For $\varepsilon>0$, choose $n_{1}$ such that $n_{1}\varepsilon>4$. Now, let $n_{0}=max \{ 3, n\}$ so that $|a_{n}|<\varepsilon$ for all $n > n_{0}$.

(e) For $a_{n}=\frac{n!}{n^{n}}$, the sequence $(a_{n})_{n=1}^{\infty}$ converges to 0. (Exercise!)

In all the above examples, we somehow guessed in advance what a sequence converges to. But, suppose we are not able to do that and one asks whether it is possible to decide if the sequence converges to some real number. This can be helped by the following analogy: Suppose there are many people coming to Delhi to attend a conference. They might be taking different routes. But, as soon as they come closer and closer to Delhi the distance between the participants is getting smaller.

This can be paraphrased in mathematical language as:

Theorem. If $(a_{n})_{n=1}^{\infty}$ is a convergent sequence, then for every $\varepsilon>0$, we can find an $n_{0}$ such that

$|a_{n}-a_{m}|<\varepsilon$ for all $m, n > n_{0}$.

Proof. Suppose $(a_{n})_{n=1}^{\infty}$ converges to a. Then, for every $\varepsilon$ we can find an $n_{0}$ such that

$|a_{n}-a|<\varepsilon/2$ for all $n > n_{0}$.

So, for $m, n > n_{0}$, we have

$|a_{m}-a_{n}|=|a_{n}-a+a-a_{m}|\leq |a_{n}-a|+|a-a_{m}|<\varepsilon$. QED.

The proof is rather simple. This very useful idea was conceived by Cauchy and the above theorem is called Cauchy criterion for convergence. What we have proved above tells us that the criterion is a necessary condition for convergence. Is it also sufficient? That is, given a sequence $(a_{n})_{n=1}^{\infty}$ which satisfies the Cauchy criterion, can we assert that there is a real number to which it converges? The answer is yes!

We call a sequence $(a_{n})_{n=1}^{\infty}$ monotonically non-decreasing if $a_{n+1} \geq a_{n}$ for all n.

Theorem. A monotonically non-decreasing sequence which is bounded above converges.

Proof. Suppose $(a_{n})_{n=1}^{\infty}$ is monotonic and non-decreasing. We have $a_{1} \leq a_{2} \leq \ldots \leq a_{n} \leq a_{n+1} \leq \ldots$. Since the sequence is bounded above, $\{ a_{k}: k=1, \ldots\}$ has a least upper bound. Let it be a. By definition, $a_{n} \leq a$ for all n, but for $\varepsilon>0$ there is at least one $n_{0}$ such that $a_{n_{0}}+\varepsilon>a$. Therefore, for $n > n_{0}$, $a_{n}+\varepsilon \geq a_{n_{0}}+\varepsilon>a\geq a_{n}$. This gives us $|a_{n}-a|<\varepsilon$ for all $n \geq n_{0}$. QED.

We can similarly prove that: A monotonically non-increasing sequence which is bounded below is convergent.

Suppose we did not have the condition of boundedness below or above for a monotonically non-increasing or non-decreasing sequence respectively, then what would happen? If a sequence is monotonically non-decreasing and is not bounded above, then given any real number $M>0$ there exists at least one $n_{0}$ such that $a_{n_{0}}>M$, and hence $a_{n}>M$ for all $n > n_{0}$. In such a case, we say that $(a_{n})_{n=1}^{\infty}$ diverges to $\infty$. We write $\lim_{n \rightarrow \infty}a_{n}=\infty$. More generally, (that is, even when the sequence is not monotone), the same criterion above allows us to say that $\{ a_{n}\}_{n=1}^{\infty}$ diverges to $\infty$ and we write $\lim_{n \rightarrow \infty}a_{n}=\infty$. We can similarly define divergence to $-\infty$.

We make a digression here: In case a set is bounded above, then we have the concept of least upper bound. For any set A or real numbers, we define supremum of A as

$sup \{ x: x \in A\}=sup A = least \hspace{0.1in} upper \hspace{0.1in}bound \hspace{0.1in} of \hspace{0.1in} A$, if A is bounded above and is equal to $\infty$ if A is not bounded above.

Similarly, we define infimum of a set A as

$inf \{ x: x \in A\}= inf A= greatest \hspace{0.1in} lower \hspace{0.1in} bound \hspace{0.1in} of \hspace{0.1in}A$, if A is bounded below, and is equal to $-\infty$, if A is not bounded below.

This would help us to look for other criteria for convergence. For any bounded sequence (a_{n})_{n=1}^{\infty} of real numbers, let

$b_{n} = \sup \{ a_{n}, a_{n+1}, a_{n+2}, \ldots\}=\sup \{ a_{k}: k \geq n\}$.

It is clear that $(b_{n})_{n=1}^{\infty}$ is now a non-increasing sequence. So, it converges. We set

$\lim_{n \rightarrow \infty}b_{n}=limit \hspace{0.1in} superior \hspace{0.1in} of \hspace{0.1in} the \hspace{0.1in} sequence \hspace{0.1in} (a_{n})_{n=1}^{\infty}= \lim \sup a_{n}= \overline{\lim}_{n}a_{n}$,

Similarly, if we write

$a_{n}=\inf \{ a_{n}, a_{n+1}, \ldots\}=\inf \{ a_{k}: k \geq n\}$,

then $(a_{n})_{n=1}^{\infty}$ is a monotonically non-decreasing sequence. So we write

$\lim_{n \rightarrow \infty}c_{n}=limit \hspace{0.1in} inferior \hspace{0.1in} of \hspace{0.1in} the \hspace{0.1in} sequence \hspace{0.1in} (a_{n})_{n=1}^{\infty}= \lim \inf a_{n}= \underline{\lim}_{n}a_{n}$,

We may not know a sequence to be convergent or divergent, yet we can find its limit superior and limit inferior.

We have in fact the following result:

Theorem.

For a sequence $(a_{n})_{n=1}^{\infty}$ of real numbers, $\underline{\lim}a_{n} \leq \overline{\lim}a_{n}$.

Further, if $l=\underline{\lim}a_{n}$, and $L=\overline{\lim}a_{n}$ are finite, then $l=L$ if and only if the sequence is convergent.

Proof.

It is easy to see that $l \leq L$. Now, suppose l, L are finite.If $l=L$ are finite. If $l=L$, then for all $\varepsilon >0$ there exists $n_{1}, n_{2}$ such that

$l - \varepsilon< \sup_{k \geq n} a_{k}< l + \varepsilon$ for all $n \geq n_{1}$ and $l - \varepsilon < \inf_{k \geq n} < l + \varepsilon$ for all $n > n_{2}$.

Thus, with $n_{0}=max{n_{1},n_{2}}$ we have

$l - \varepsilon for all $n > n_{0}$.

This proves that equality holds only when it is convergent. Conversely, suppose $(a_{n})_{n=1}^{\infty}$ converges to a. For every $\varepsilon > 0$, we have $n_{0}$ such that $a-\varepsilon for all $n > n_{0}$. Therefore, $\sup_{k \geq n}a_{k} \leq a+\varepsilon$ and

$a-\varepsilon \leq \inf a_{n}$ for all $n \geq n_{0}$. Hence, $a-\varepsilon \leq < L \leq a+\varepsilon$. Since this is true for every $\varepsilon > 0$, we have $L=l=a$.

QED.

Real Numbers, Sequences and Series: Part 7

Exercise.

Discover (and justify) an essential difference between the decimal expansions of rational and irrational numbers.

Giving a decimal expansion of a real number means that given $n \in N$, we can find $a_{0} \in Z$ and $0 \leq a_{1}, \ldots, a_{n} \leq 9$ such that

$|x-\sum_{k=0}^{n}\frac{a_{k}}{10^{k}}|< \frac{1}{10^{n}}$

In other words if we write

$x_{n}=a_{0}+\frac{a_{1}}{10}+\frac{a_{2}}{10^{2}}+\ldots +\frac{a_{n}}{10^{n}}$

then $x_{1}, x_{2}, x_{3}, \ldots, x_{n}, \ldots$ are approximate values of x correct up to the first, second, third, …, nth place of decimal respectively. So when we write a real number by a non-terminating decimal expansion, we mean that we have a scheme of approximation of the real numbers by terminating decimals in such a way that if we stop after the nth place of decimal expansion, then the maximum error committed by us is $10^{-n}$.

This brings us to the question of successive approximations of a number. It is obvious that when we have some approximation we ought to have some notion of the error committed. Often we try to reach a number through its approximate values, and the context determines the maximum error admissible. Now, if the error admissible is $\varepsilon >0$, and $x_{1}, x_{2}, x_{3}, \ldots$ is a scheme of successive is approximation of a number x, then we should be able to tell at which stage the desired accuracy is achieved. In fact, we should find an n such that $|x-x_{n}|<\varepsilon$. But this could be a chance event. If the error exceeds $\varepsilon$ at a later stage, then the scheme cannot be a good approximation as it is not “stable”. Instead, it would be desirable that accuracy is achieved at a certain stage and it should not get worse after that stage. This can be realized by demanding that there is a natural number $n_{0}$ such that $|x-x_{n}|<\varepsilon$ for all $n > n_{0}$. It is clear that $n_{0}$ will depend on $varepsilon$. This leads to the notion of convergence, which is the subject of a later blog.

More later,

Nalin Pithwa