Chapter - 6, Mathematical Induction

Section - 6.4 - Strong Induction


Summary

  • To prove a goal of the form :
    Prove that , where both and range over the natural numbers in this statement. Of course, the most direct way to prove this is to let be an arbitrary natural number, assume that , and then prove .

  • Note that no base case is necessary in a proof by strong induction. All that is needed is a modified form of the induction step in which we prove that if every natural number smaller than has the property , then has the property . In a proof by strong induction, we refer to the assumption that every natural number smaller than has the property as the inductive hypothesis.


Soln1

(a)

() Suppose . Suppose is an arbitrary natural number. Since is natural number it follows is also a natural number. Thus is true. Since , it follows . Thus for , is true. Since is arbitrary, it follows .

() Suppose . It follows that is true. Thus is true.

(b)

By ordinary induction:

Base Case:

For , is true because is a natural number and there is no value of . Thus the statement is vacuously true. Since is true(given), it follows that is true by modus ponens.

Induction Step:

Suppose is true. It follows that . But it is given that . Thus is true. Thus is true. It follows that is true.

Thus if is true then is also true.


Soln2

To Prove: .
Or we can say , where .

Suppose is an arbitrary natural number. Suppose where . Thus this is our induction hypothesis.

Note: We are using strong induction. Thus after assuming our induction hypothesis: , we will prove that is true. Proving will complete the proof.

Since is natural number, it follows . Thus we have to prove . We shall prove this by contradiction. Thus lets suppose . Thus there exist a such that . From the example-6.4.5 from book, it follows that is even. Thus there are such that and . Since , it follows . Since , it follows . Thus there exists a such that . But this contradicts with our induction hypothesis. Thus our assumption that is true is wrong. Thus . It follows that is true.


Soln3

(a)

We will prove this by contradiction. We can follow the approach in Soln2 or we can also follow the approach used in book in example-6.4.5. Lets follows the approach used in example 6.4.5. Thus we will be using Well ordering principle.

Suppose is rational. Thus . Thus the set is not empty. Suppose is the smallest element of this set. Thus there exist such that . Thus . It follows that is even. Since is even it follows that is even. Thus suppose . Thus . Since , it follows , or . It follows that is also even. Thus for some . It follows . Also . Thus . But this contradicts with the assumption that is the smallest element. Thus is irrational.

(b)

Suppose is rational. Thus . Suppose are the elements such that . Thus:



Thus is rational. But this contradicts with part(a). Thus is irrational.


Soln4

We need to prove that .

Suppose . Thus we need to prove .

Suppose is an arbitrary natural number. Suppose is our induction hypothesis. Thus we have following possible cases:

  • Case :
    Since , it follows is false. Thus is vacuously true.

  • Case :
    Clearly . Thus is true.

  • Case : Clearly . Thus is true.

  • Case : Clearly . Thus is true.

  • Case : Thus . Since , it follows from induction hypothesis that is true. Thus there exist some and such that . Thus , or . It follows that is true.


Soln5

We need to prove is integer. Suppose is an arbitrary integer. Suppose our induction hypothesis is is an integer. Thus we have following possible cases:

  • Case :
    Clearly is vacuously true.

  • Case :
    We are given that is integer. Thus is true.

  • Case :
    Consider the product: . Since , it follows by our induction hypothesis that is an integer. Thus is also an integer.

    On simplifying .

    Thus is also an integer since is integer and is integer.

Thus from all cases is true.


Soln6

(a)

Suppose is arbitrary natural number. Suppose .

  • Case
    . Thus is true.

  • Case . Clearly is a natural number and . Thus by induction hypothesis,

    Thus .
    Thus is also true.

Thus from both cases, is true.

(b)

Suppose is arbitrary natural number. Suppose .

  • Case
    . Thus is true.

  • Case . Clearly is a natural number and . Thus by induction hypothesis,

    Thus .
    Thus is also true.

Thus from both cases, is true.

(c)

Suppose is arbitrary natural number. Suppose .

  • Case
    . Thus is true.

  • Case . Clearly is a natural number and . Thus by induction hypothesis,

    Thus .
    Thus is also true.

Thus from both cases, is true.

(d)

I made a guess as it is similar to part(c) for this formulae . But it does not cover the case for , so adjusted the formulae to .

Suppose is arbitrary natural number. Suppose .

  • Case
    . Thus is true.

  • Case . Clearly is a natural number and . Thus by induction hypothesis,

    Thus .
    Thus is also true.

Thus from both cases, is true.


Soln7

(a)

Suppose is arbitrary. Suppose . We have following possible cases:

  • Case
    Clearly is false. Thus statement is vacuously true. Thus is true.

  • Case
    . Thus is true.

  • Case
    (fibonacci number). Thus is true.

  • Case
    Thus and . Since is a fibonacci number, . Since and and , it follows by induction hypothesis and . Thus:





    Thus is true.

Thus from all cases is true.

(b)

Suppose is arbitrary. Suppose . We have following possible cases:

  • Case
    Thus . We have:
    , (fibonacci numbers property)
    , (by induction hypothesis)

  • Case
  • Case
    For both of these cases, it can be directly verified by putting the values for .

(c)

Both parts can be proved easily by putting in part(a) and putting in part(b).

(d)

We need to prove following:

.

Suppose are arbitrary natural numbers such that for some natural number . Suppose . We have following possible cases:

  • Case
    Since , it follows . Thus for , .

  • Case
    We have . Since , it follows is a natural number. Thus we can apply part(a). Applying part(a), we get .

    Since , it follows . Thus is a multiple of . Or we can say , where . Since and , it follows from the induction hypothesis, there exist some natural number such that .

    Thus , or . Thus for , we have .

  • Case
    Since , for some natural number , it follows that this case is not possible.

(e)

Suppose is arbitrary natural number. Suppose:


We know that . Thus we have following possible cases:

  • Case :
    Thus .
    Also .

  • Case :
    Thus .
    Also .

  • Case :

    Since , it follows and . Thus and are both valid fibonacci numbers.

    Since is a fibonacci number, it follows:

    Since , it follows is a natural number. Since and is a natural number, it follows from the induction hypothesis:

    and

    Thus :


    We can see above many pairs of the form of and . Thus we can use the theorem . Thus except the first and last term all the pairs in the above summation can be combined. Thus after combining we get the following:




Thus is true in all cases.

Similarly we can prove for .


Soln8

(a)

We need to prove the following:

() Suppose is an arbitrary integer. Suppose . Since , it follows that . Thus , or .

If then . Thus . Since is not defined.

Since and , it follows . Thus .

() Suppose . It follows , or .

(b)

Suppose and . Thus from part(a) we know that .

Suppose is a arbitrary natural number. Since , or it follows:


Thus . Thus:


But and


Thus is a gibonacci sequence.

(c)

Scratch Work

We will first compute and by assuming that formulae is correct.

Thus for , we have . Or .
Similarly for , we have . Or .
Thus we get .

Thus and . We have two equations with two unknowns and .

Solving them gives:

Now suppose and .

Suppose is an arbitrary natural number. Suppose . Thus we have following possible cases:

  • Case :
    Clearly . Thus .

  • Case :
    Clearly . Thus .

  • Case :
    We have . From part(a) we know and . It follows



    Thus .

Thus for all cases .


Soln9

Since it is a gibonacci sequence and and is given. We can use part(c). Thus , where and .

Thus
and

Thus , where are from Soln8.


Soln10

Lets suppose which is similar to Soln8 except negative sign. Addition will also generate same result but it appears from the formulae that negative sign may help.

Now we have:

Using , we have and .

Now using our assumption,



Thus we have four equations and four unknowns .

Using first and seconds equation we can find values of and in terms of and . Thus we get:

Now putting these values of and in and equation:
In equation: , or . Thus .
and In equation: , or .
Using ,

Using :
we get .

Thus with and and eliminating , we get the quadratic equation . Solving it gives . Since , we get .

Thus we have two pair of values for or .

With , we get and . Thus . Using , we get and . Thus .

Thus from both values we get the same formulae .

Lets prove that formulae is correct:

Suppose is arbitrary natural number. Suppose . Thus we have following possible values of :

  • Case
    . Thus .

  • Case
    . Thus .

  • Case
    Since , by induction hypothesis . Similarly since , by induction hypothesis we get .

    Thus





    Thus .

Thus from all the cases.


Soln11

Suppose is an arbitrary natural number. Suppose . Thus we have following possible cases:

  • Case
    Clearly from the given values are fibonacci numbers.

  • Case
    We have


    Since and , thus by our induction hypothesis, we have .

    Thus .

Thus the given sequence is fibonacci sequence.


Soln12

Suppose is an arbitrary natural number. Suppose . We have following possible cases:

  • Case
    Clearly . Thus number of elements are . Thus .

  • Case
    Clearly . Thus number of elements are . Thus .

  • Case
    We can easily see that will contain all the elements contained in and all elements of the set . Since , it does not contain the element: “”. Thus will not have any consecutive numbers.
    Clearly number of elements in is same as number of elements in . Thus total number of elements:
    .
    Since and , it follows by induction hypothesis, and . Thus .

Thus from all the cases we get .


Soln13

(a)

Suppose is an arbitrary integer. Consider the following cases:

  • Case
    Clearly it follows from the theorem 6.4.1 from the book that and .

  • Case
    Since , it follows . Thus from theorem 6.4.1:





    , where and .

    Since , it follows that , or .

(b)

Suppose and are integers such that:
, where .
and and .
It follows that .
Thus .

Suppose , where is an integer. Thus we get:

We have following possible cases:

  • Case
    It follows . Thus .
    Since . Thus . Since , it follows .

    Since and , it follows that . Thus it is a contradiction since .

    Thus this case is not possible.

  • Case .
    Since , it follows . Also since , it follows .

Thus from all possible cases and . Thus we can conclude that and are unique integers.

(c)

Suppose is an arbitrary integer. From part(a), we can easily deduce that if , then such that . It follows that there are only two possible values() of . Thus if , it follows and if , it follows .

Clearly if , then is an even integer. and if then is an odd integer.

Also from part(b), since , then and are unique. Thus only one case is possible i.e. either is even or is odd but not both.

Since is arbitrary, it follows that every integer is either even or odd but not both.


Soln14

Suppose is the maximum of and . Suppose is an arbitrary integer. Thus by the division algorithm we can choose unique and such that and .

Suppose . Thus . Since , it follows . Thus which is a contradiction. Thus , or .

Suppose . Thus . Thus which is a contradiction. Thus .

Since , it follows . Since and , it follows .

Thus . Thus .

From example 6.1.3, we know that , if . Since , it follows . Since , it follows .

Since and , it follows . Since , it follows .


Soln15

(a)

Suppose is a positive integer. Suppose .

Since , it follows from induction hypothesis that there exist some and such that .

Since , it follows that for some and , .

Now consider
(By triangle inequality)
for all (By induction hypothesis for k-1)
for all where is maximum of and
where

Thus where .

(b)

From Ex14 part(a), we know that for every positive integer , for some positive integer . It follows that functions , , … belongs to O(g) where .

Now the required proof directly follows from part(a) of this solution.


Soln16

(a)

By division algorithm we know that for some and , where .

Also since , it follows that for some , . Putting in , we get:



Thus s’ = 1-sq t’ = -tq r = s’a + t’b $$.

Since , we have two cases:

  • Case
    Thus or . It follows that . Since is the smallest element in , it follows . But this contradicts with . Thus is not possible.

  • Case
    Thus . Thus . It follows . Thus .

Similarly it can be proved that .

(b)

Since , it follows that for some integer , . Similarly since , it follows that for some integer , .
Since , it follows that . Thus . Thus .

Also since from part(a), divides both and . Thus any number which divides and must divides . Thus . It follows that is greatest common divisor of and .


Soln17

(a)

Suppose are natural numbers such that and is prime. Suppose is the greatest common divisor of and . Thus from Ex-16 part(b), for some integers . Since divides and is a prime number, there are following possible cases:

  • Case
    Since is greatest common divisor of and , it follows divides . Since , it follows divides , or .

  • Case
    Since , it follows . Since , it follows for some integer , . Thus . Putting in , we get , or , or . Thus .

Thus from both cases, either or .

(b)

Suppose is arbitrary. Suppose .

Suppose , or . Thus from part(a), it follows either either or .

Since , it follows from induction hypothesis that if , then .

Thus it follows that .


Soln18

Base Case:

Suppose . Since and is prime it follows that . Thus .

Induction Step:

Suppose for and for all , if , then and where .

Now suppose . Clearly , since if then . Thus will not be prime.

Note: is same in last two statements. But is different. In former statement if , but in the later statement above, may or may not be equal to . Or first statement is hypothesis and second statement is which we shall prove to be true if hypothesis is true.

Clearly . It follows . Thus from Ex17 part(b), it follows , where . But . Thus .

Also since , it follows . Thus from Ex17 part(b), it follows , where . But . Thus .

Thus . Now since , it follows .

But from the induction hypothesis, if then and . Thus .

Thus if , then and .


Soln19

Since , it follows .

Thus it appears that .

Now we shall prove the formulae is correct.

Base Case:

For , .

Induction step:

Suppose formulae is correct for . Thus .

Thus


Using hypothesis:
,

Thus is true if is true.


Soln20

It appears from above table that formulae is .

Proof:

Base Case:

For , it follows directly from the table.

Induction Step:

Suppose it is true for . Thus .

Now



.

Thus if is true then is also true.