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 example6.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 example6.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 k1)
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’ = 1sq 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 Ex16 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.