Chapter - 6, Mathematical Induction

Section - 6.3 - Recursion


Summary

Note: In this book natural numbers include also. But it seems like in some places in the proofs, I messed up with this convention. In some placed I might have considered includes while in other places vice versa. Please point out to me, I will correct to use the books version of in all the places.

  • Recursive functions are defined in the following way:
    • For some values, x, f(x) is given.
    • For values other then given, f(x) is defined by calling itself for lower/upper values.
    • Thus by recursively tracing down he values we reach to a value for which f(x) is given and then move back filling in the corresponding values.
  • This section shows that recursion and induction are similar by using some examples.

Soln1

Lets try by putting some values:

Thus it appears that .

Lets prove this by mathematical induction.

Base Case:

It is directly clear from above table.

Induction step:

Suppose it is true for . Thus .

Now for :

We have . Using induction hypothesis , we get:

.
.
.
.
.
.

Thus if is true, then is also true. Thus formulae is correct.


Soln2

Base Case:

For , we have . Thus is true.

Induction Step:

Suppose theorem is correct for . Thus .

Now for , we have:

.
Using induction hypothesis:
.
.
.
.
.
.
.
.

Thus if is true, then is also true.


Soln3

Base Case:

For , we have .

Thus is true.

Induction step:

Suppose theorem is correct for . Thus .

Now for , we have:

.
Using induction hypothesis:
.
.
.
.
.
.
.
.

Thus if is true, then is also true.


Soln4

Base Case:

For , we have .

Thus is true.

Induction Step:

Suppose theorem is correct for . Thus .

Now for , we have:
.
.
.
.
.
.
.
.

Thus if is true, then is also true.


Soln5

Suppose is an arbitrary real number.

Base Case:

For , we have .

Induction Step:

Suppose theorem is correct for . Thus .

Now for , we have:
.
.
.
.
.
.

Thus if is true, then is also true.


Soln6

Base Case:

For , we have . Also .
Thus 2 - \frac 1 n $$.

Induction Step:

Suppose theorem is correct for . Thus 2 - \frac 1 n $$.

Now for , we have:

.
.
.
.
.
.

Thus if is true, then is also true.


Soln7

(a)

Base Case:

For , we have .

Induction Step:

Suppose it is true for . Thus .

For , we have:

.
.
.
.

Thus if is true, then is also true.

(b)

Base Case:

For , we have .

Induction Step:

Suppose it is true for . Thus .

For , we have:

.
.
.

Thus if is true, then is also true.


Soln8

(a)

Suppose is arbitrary natural number.

Base Case:

For , we have .

Induction Step:

Suppose theorem is correct for . Thus .

For , we have:

.
.
.
.
.
.
Since ,
.
.
.

Thus if is true, then is also true.

(b)

Base Case:

For , we have .

Induction step:

Suppose theorem is correct for . Thus .

Since . Thus applying part(a), we have:

.

Thus .
By induction hypothesis,
. .

Thus if is true, then is also true.

(c)

We know that .

Thus using part(b) . Now from part(a) we can see that is a increasing sequence. Thus


Soln9

Base Case:

For , we have .

Induction Step:

Suppose theorem is true for . Thus .

Now for , we have .
.
.
.
.
.
.
.
.
.
.

Thus if is true, then is also true.


Soln10

Lets try by putting some values:

Thus it appears that .

Base Case:

It directly follows from above table.

Induction Step:

Suppose it is correct for . Thus .

For , we have:

.
.
.

Thus if is true, then is also true.


Soln11

Lets try by putting some values:

Thus it appears that .

Base Case:

It directly follows from above table.

Induction Step:

Suppose it is correct for . Thus .

For , we have:

.





Thus if is true, then is also true.


Soln12

(a)

If we prove that , then it is easily followed that .

Base Case:

For , we have . Thus is true.

Inductive step:

Suppose theorem is correct for . Thus .

For , we have .

Thus we can conclude . It follows .

(b)

Base Case:

For . We have .

Induction Step:

Suppose theorem is correct for . Thus .

For , we have:



By induction hypothesis,




Thus if is true, then is also true.


(c)

Base Case:

For , we have .

Induction step:

Suppose theorem is correct for . Thus .

Now consider for , we jave:

.
From part(a), , we have:

.
.
.
.
.


Soln13

(a)

Base Case:

For , we have .

Induction Step:

Suppose theorem is correct. Thus .

For , we have :




Thus if is true, then is also true.

(b)

Base Case:

Putting in part(a), we get . Thus for the given theorem if we assume , then is follows is correct.

Induction Step:

Suppose theorem is correct. Thus .

Now consider :



Since ,

Since is positive integer,

Thus if is true, then is also true.


Soln14

Suppose is an arbitrary real number. Suppose is arbitrary integer.

Base Case:

For , we have .

Induction step:

Suppose theorem is correct for . Thus .

Thus


Thus if is true, then is also true.


Soln15

Base Case:

For , .

Induction Step:

Suppose theorem is correct for . Thus .

Now,




Thus if is true, then is also true.


Soln16

Lets try by putting some values:

Thus it appears that .

Base Case:

It directly follows from table.

Induction step:

Suppose theorem is correct for . Thus .

Now



Thus if is true, then is also true.


Soln17

Thus it appears that .

Base Case:

It directly follows from table.

Induction step:

Suppose theorem is correct for . Thus .

Now



Thus if is true, then is also true.


Soln18

(a)

Expanding .

Also .

Thus .

(b)

Lets compute







Hence proved.

(c)

Base Case:

For . Suppose has a set with elements. Thus only possible value of . Thus number of subsets of containing elements are (empty set). Also .

Induction Step:

Suppose theorem is correct if has elements. Thus number of sized subsets from are .

Now suppose is a set of elements. Suppose is an arbitrary element of . Suppose . Suppose is an integer such that . We have following possible cases:

  • Case 1:
    Clearly there is only one possible zero sized subset of . Also, . Thus for , number of subsets of is same as .

  • Case 2:
    Since contains elements, it follows that there is only one subset of containing elements(subset is itself). Since , it follows number of subsets of of elements is same as .

  • Case 3:
    There are two types of -sized subsets of . One type of subsets contain and other type does not contain .

    • Subsets that does not contain are also the subsets of . Now since has elements and , it follows by induction hypothesis that number of such subsets are .

    • Subsets that contains are of the form of where is -sized subsets of . Thus number of -sized subsets of that contains is equal to number of sized subsets of . Since contains elements, it follows from induction hypothesis that the number of subsets is .

    Thus total number of -sized subsets of are . From part(b) this sum is equivalent to .

Thus from all the cases, total number of sized subsets of is .

(d)

Base Case:

For , LHS = . And RHS = . Thus .

Induction Step:

Suppose theorem is correct for . Thus .

For , we have . Thus by induction hypothesis:


Multiplying each term inside by and using ,




Thus if is true, then is also true.


Soln19

(a)

Putting in part(d) of Ex18, we get . Thus:

(b)

Putting in part(d) of Ex18, we get . Thus:


Soln20

It will be easier to prove .

Clearly is positive, it follows is also positive.

Base Case:

For , . Clearly .

Induction Step:

Suppose theorem is correct for .

Now


Thus . Or we can also say that .


Soln21

Adding helped made LHS closer to RHS. TODO