Chapter - 6, Mathematical Induction

Section - 6.2 - More Examples


Summary

  • This section covers more examples for mathematical induction to show that this proof technique is just not limited to natural numbers as shown in last section. It covers examples to show a wide range of uses of proof by mathematical induction.

Soln1

Given:

  • is a set consisiting of elements.
  • is a partial order on .
  • From first example of this section in book, we know there must exist a minimal element in . Lets call that minimal element as .
  • .
  • .

Once we proved in part(a) that is a partial order. Then by induction hypothesis there must exist some relation such that it is a total order on .

  • is a total order on .
  • .

(a)

To prove that is partial order we need to prove that is reflexive, transitive and antisymmetric.

Reflexive:

Suppose . Then . Since is reflexive, it follows . Since , it follows . Thus , or . Thus is reflexive.

Antisymmetric:

Suppose . Thus . Since is partial order, it follows . Thus . It follows is antisymmetric.

Transitive:

Suppose and . Thus . Since is partial order, thus is transitive. It follows . Since and , it follows . Since and , it follows . Thus is transitive.

(b)

To prove is total order, we need to prove is partial order and . To prove is partial order, we need to prove is reflexive, transitive and antisymmetric:

Reflexive:

Suppose . We have two possible cases:

  • Case 1:
    Thus . It follows .

  • Case 2:
    Thus . Since is total order on , it follows is reflexive and . Thus .

Thus from both cases . Thus is reflexive.

Transitive:

Suppose . We have following possible cases:

  • Case 1:
    Since and , it follows . Thus .

  • Case 2:
    Since . It follows and . Thus . Thus . Since and , it follows and . Thus and . Since is total order, it follows . Thus .

Thus from all possible cases , or is transitive.

Note that here we need not to consider possible values of as cases: and already covers those possible values.

Antisymmetric:

Suppose . Thus we have two possible cases:

  • Case 1:
    Thus . It follows directly that if then .

  • Case 2:
    Thus . Since is total order. It follows if then .

Thus from both cases if then .

Thus we have proved that is partial order.

Now to prove is total order, we need to further prove that: .

Suppose and . Thus we have following possible cases:

  • Case 1: .
    Thus . It follows .

  • Case 2: .
    Thus . It follows .

  • Case 3: .
    Thus . Since is total order on , it follows . Thus .

Thus from all possible cases .

Thus is total order.

Now we are left to prove that .

Suppose such that . Thus we have following cases:

  • Case 1: .
    Thus . It follows .

  • Case 2: .
    Thus . But since is minimal element of , it follows that . Thus this case is not possible.

  • Case 3: .
    Thus . Since , it follows . Since , it follows that .

Thus from all the cases if then . It follows that .


Soln2

Base Case: Suppose and . Clearly . Since , is partial order on . Since , it follows that is true.

Induction Step:

Suppose the conclusion is true for any set with elements.

Now suppose such that has elements. Suppose is an arbitrary element of . Consider the set . Thus has elements and thus by induction hypothesis, there exist a relation such that is partial order on and and . Suppose and . Now consider the relation . Now to prove this step we shall prove the following:

  • is partial order on .
  • .
  • .

To prove is partial order on , we need to prove that it is reflexive, transitive and antisymmetric.

Reflexive:

Since , and is reflexive, it follows that is reflexive.

Transitive:

Suppose . We have following possible cases:

  • Case 1: .
    Clearly since is transitive, . Thus .

  • Case 2: .
    Since , it follows and . Thus by the definition of , . Since and and is transitive, it follows . Since , then by definition of , . Since and , it follows . Thus .

  • Case 3: .
    This case is not possible since and . But and are disjoint by the definition.

  • Case 4: .
    Thus and . We will prove by contradiction that . We have only two possibilities: either or . Suppose . Thus . Since and and is transitive, it follows . Since , then by definition of , it follows . Since and are disjoint it follows cant be in both sets and . Thus it contradicts our assumption that . Thus . Since and , it follows . Thus .

Thus from all cases . Thus is transitive.

Antisymmetric:

Suppose and . Thus we have following cases:

  • Case 1: .
    Since is antisymmetric, it follows that .

  • Case 2: .
    Since , it follows . Since and , it follows . Thus . But it contradicts with . Thus this case is not possible.

  • Case 3: .
    Since , it follows . Since and , it follows . Thus . But it contradicts with . Thus this case is not possible.

  • Case 4: .
    This case is not possible since , thus can not belong to both and .

Thus from all possible cases, is antisymmetric.

Since is reflexive, transitive and antisymmetric, it follows that is partial order on .

Also clearly since and , it follows .

Now we shall prove the last part: .

Suppose and . We have two cases:

  • Case 1: and .
    Since , it follows . Since , it follows . Since , it follows .

  • Case 2: and .
    Since , it follows . Since , it follows . Since , it follows .

  • Case 3: .
    Since and , it follows . Thus by induction hypothesis for set of elements, we have . Since , it follows .

Thus from all the possible cases we have . Since are arbitrary, it follows .


Soln3

Base Case:

Suppose and it contains only one element say . Thus clearly is true. Thus is the -smallest element.

Induction Step:

Suppose if contains elements then conclusion is true i.e. there exist a -smallest element of .

Now suppose and it contains elements. Suppose is arbitrary element of and . Thus contains elements. Thus by induction hypothesis, has a -smallest element say .

Since is total order on , we have following possible cases:

  • .
    Suppose . Now if then . Since is smallest element in , it follows . Since and , it follows .
    Now suppose if . Since is total order, it follows . Since , it follows .
    Thus in either case, . Since is arbitrary, it follows that is the -smallest element of .

  • .
    Suppose . Now if then . Since is smallest element in , it follows .
    Now for the case if , then clearly is equivalent to .
    Thus from either case . Since is arbitrary, it follows is the smallest element of .

Thus from all possible cases, there exist an smallest element of .


Soln4

Base Case:

Suppose such that it contains only one element say . Since is reflexive, . It follows . Since is the only element in , it follows .

Induction Step:

Suppose conclusion is true if such that it contains elements.

Now consider consisiting of elements. Suppose and . Thus consists of elements. Thus by induction hypothesis, there exist some such that . Now we have following possible cases:

  • .
    Thus clearly is true. Thus there exist such that .

  • .
    Suppose . Now either or . If , then since is reflexive, .

Now for the case when , then . Thus . Thus there exist some element such that and . Since we are given that , it follows either or . Suppose . Then since and , it follows . But . Thus the assumption is wrong. Thus . Since and , it follows .

Since is arbitrary, it follows .

Thus from both cases, there exist some element such that is true.

(b)

Suppose the set of contestants.

Suppose . Clearly . Thus we can apply part(a). Thus there exist a contestant say such that .

Clearly is an excellent contestant.


Soln5

Base Case:

For , we have: . Also . Thus is true.

Induction Step:

Suppose for theorem is correct. Thus is true. Thus .

Now consider for ,

.
.
.
Since ,
.
.
.
But by induction hypothesis, .
.
.

Thus .
Thus is true.


Soln6

Base Case:

For , clearly .

Induction step:

Suppose

Now consider . By triangle inequality:
.
Thus by induction hypothesis:
.

Thus is true if is true.


Soln7

(a)

Suppose are positive real numbers. It follows that . Thus .
Or . We know that . Dividing both sides by , we get:
.

(b)

Suppose . Thus and . Thus:
.
. Dividing by , we get:
.
.

(c)

Base Case:

For , we have . Clearly from part(a) we can say that .

Induction Step:

Now suppose is true. Thus .

Now consider . This is equivalent to:

.
.
Using induction hypothesis for , we get:
.
Since . By part(b) of the solution . Thus:
.

Thus . Thus is true if is true.


Soln8

(a)

We know that . Thus:

.
.
.
.
.
.
Since , it follows . Thus:
.

(b)

Base Case:

Clearly for from part(a) theorem is correct.

Induction Step:

Suppose theorem is correct for . Thus .

Now consider the sum .

By induction hypothesis, clearly .

Also by induction hypothesis, .

Thus we have:

.

Suppose and .

Thus , it follows from part(a) that .

It follows:

.
.
.
.
.
.

Thus is also true if is true.

(c)

Base Case:

This directly follows from the assumption in the problem at . Thus:

.

Induction step:

Suppose theorem is true for . Thus .

Now suppose and .

Thus .
Or .
Or .
Or .
Or .

Also since , it follows .

Thus we have .

Thus .

Thus is true if is true.

(d)

We shall prove this by contradiction. Suppose the inequality is not correct for some . Now suppose is an integer such that . Thus by part(c) it follows theorem fails for . But from part(b) contradicts this as it says theorem is correct for . Thus our assumption is wrong and the theorem is correct for all values of .


Soln9

From Soln8, we have .

We know that if then . Thus:

.

Suppose .

.

.


Soln10

Base Case:

Suppose has . Then . Thus contains element.

Induction Step:

Suppose the theorem is true for . Thus for a set containing elements, number of elements in equals to .

Suppose contains elements. Suppose is an arbitrary element of . Suppose . Thus contains elements. Since , it follows . Every subset of may either contain or not. Thus half of the subsets of will contain and other half will not. Since , subsets os that does not contain are also the subsets of . Since number of subsets of , it follows number of subsets of not containing is also . It follows number of subsets of containing is also . Thus total subsets of .

Thus if P(n) is true then is also true.


Soln11

Base Case:

For , has elements. Also .

Induction Step:

Suppose theorem is correct for elements. Thus contains elements.

Suppose contains elements. Suppose is an arbitrary element of . Suppose . Thus contains elements. Thus by induction hypothesis contains elements.

Clearly contains all the elements of . In addition contains all the subsets of containing exactly two elements such that each subset contains . If is combined with every element of then the result is the same as all the subsets of containing exactly two elements that contains . Since number of elements in is , it follows number of subsets of containing exactly two elements such that each set contains is equal to . Thus number of elements in is equal to sum of number of elements in and (number of elements in ). Thus number of elements in is equal to .

Thus is also true if is true.


Soln12

Base Case:

For , we have . Clearly if any of the four triangles(thus any corner) is removed then the remaining shape is same as the trapezoidal tile. Thus for theorem is correct.

Induction step:

Suppose theorem is correct for . Thus if any equilateral triangle triangle is split into small congruent triangles and one of them is removed, then the resulting shape can be covered with trapezoidal tiles.

Now consider a equilateral triangle is cut into small congruent equilateral triangles. Thus the equilateral triangle is cut into smaller equilateral triangles. Thus we can also say there are congruent equlateral triangle say with each of the triangle contains small triangles. This can be imagined easily with one triangle on each corner(say ) of the equilateral triangle and one at the center(say . Thus in a way this center triangle is splitting the main triangle into 4 equal triangles and each corner of the center triangle touches midpoint of each side of the main triangle.

Now suppose a triangle of the equal triangles is removed from the corner of the main equilateral triangle. Thus this small triangle must belong to one of the three equilateral triangle or . Lets assume the small triangle is removed from .

Since contains equal triangles, then by induction hypothesis can be covered by trapezoidal tiles. Thus we need to prove that the remaining 3 triangles can also be covered by trapezoidal tiles.

Now consider that we place trapezoidal tile on triangles such that trapzoidal tiles covers exactly one small triangle of each triangle . This placement will result in each triangle with one smaller triangle of the corner covered. Thus now we need to cover only triangles of . Thus by induction hypothesis this can be done.

Thus whole main triangle can be covered with trapezoidal tiles.


Soln13

Base Case:

For , total number of regions by one chord in the circle .

Induction Step:

Suppose this is true for . Thus number of regions by chords .

Now consider for chords. Clearly, the way in which chord is drawn it will intersect every other chord(total ) at one point. And after the starting point of the chord, on every point of intersection, that region is divided into two parts. Thus after drawing chords, when we draw -th chord, it will divide regions into two parts. Thus extra regions are added. Thus total number of regions will be sum of number of regions created by chords and . By induction hypothesis number of regions by chords . Thus total regions created by chords are .

Thus if is true, then is also true.


Soln14

Base Case:

For , clearly it can be colored in the way required.

Induction Step:

Suppose theorem is correct for chords.

Every new chord we draw divides the circle into two parts. Also every new chord divides each region from which it passes into two parts. Now suppose a circle has chords and we draw the -th chord. Thus this -th chord will divide the circle in two parts say and . Also this -th chord divides every previous region which it passes into two parts. Clearly this division of the region is such that one region lies in and other lies in .

Now by hypothesis when chords were drawn, the region was colored correctly. It follows that after dividing the corcle in two parts then each individual part is colored correctly. Thus and are colored correctly. But when we see and combined then colors are not correct.

Since both and are correct individually, we can invert all the colors and they will still be correctly colored. Thus if we invert all the colors of only one part say . Then and both are correctly colored. Also because of the inverse of colors they will be correctly colored even if we combine them to form the circle.

Thus if is true then is also true.


Soln15

The flaw is in deducing that every natural number is an element of . Clearly was selected such that it belongs to both and , thus it is not necessary that any other , in particular, which belongs to also belongs to .


Soln16

Base case is correct.

In the induction step it assumed it is correct for . Then it proceeded for elements. Now while working with elements it is assumed that . But this assumption is not correct as it can also be the case when . Since the assumption is wrong, it follows that induction step is not correct.