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