## Chapter - 6, Mathematical Induction

### Section - 6.1 - Proof by Mathematical Induction

### Summary

- To prove a goal of the form :

First prove , and then prove . The first of these proofs is sometimes called the base case and the second the induction step. - Form of the final proof:

Base case: [Proof of goes here.] Induction step: [Proof of goes here.].

**Soln1**

By Mathematical induction:

__Base Case:__

For , . Thus is true.

__Induction Step:__

Suppose is true. Thus .

Thus we have .

.

.

.

Thus if is true then is also true.

**Soln2**

By Mathematical induction:

__Base Case:__

For , . Thus is true.

__Induction Step:__

Suppose is true. Thus .

Thus we have .

.

.

.

.

.

Thus is also true if is true.

**Soln3**

By Mathematical induction:

__Base Case:__

For , . Thus is true.

__Induction Step:__

Suppose is true. Thus .

Thus we have .

.

.

.

.

.

.

Thus is also true if is true.

**Soln4**

To find the formulae we may proceed as:

In the given series it includes only odd numbers. Consider the series containing both odd and even terms:

. Thus we have total terms. We know from soln1 sum of this = .

Clearly if we remove all the even terms from this we will get our series. Also we have even terms and odd terms. Since we will always have atleast one term( becuase ), we can think of the above modified series as consisting of pairs where each pair is one odd number and one even number with even number = 1 + odd number. Thus we have such pairs. Suppose sum of odd terms is . Then clearly since each pair consists of one odd and one even term with even term = 1 + odd term. Thus sum of even terms is sum of odd terms and total number of pairs. Thus sum of even terms = . Total sum is sum of all even and all odd terms. Thus we have . On symplifying it gives .

Thus sum of the required/given series = .

We shall prove by inductions that is correct sum.

__Base Case:__

For , . Thus is true.

__Induction Step:__

Suppose is true. Thus .

Thus we have .

.

Thus is also true if is true.

**Soln5**

By Mathematical induction:

__Base Case:__

For , . Thus is true.

__Induction Step:__

Suppose is true. Thus .

Thus we have .

.

.

.

.

.

Thus is also true if is true.

**Soln6**

By looking at Ex1 and Ex5, it seems that formulae is .

We shall prove that formulae is correct by Mathematical induction:

__Base Case:__

For , . Thus is true.

__Induction Step:__

Suppose is true. Thus .

Thus we have .

.

.

.

.

.

Thus is also true if is true.

**Soln7**

By checking the example mentioned and with some hit and try, it seems that formulae is .

__Base Case:__

For , . Thus is true.

__Induction Step:__

Suppose is true. Thus .

Thus we have .

.

.

.

.

Thus is also true if is true.

**Soln8**

First we can observe that on LHS there are terms and on RHS there are terms.

By Mathematical induction:

__Base Case:__

For . LHS will contain two terms = . And RHS will contain one term = . Thus , is true.

__Induction Step:__

Suppose is true.

Thus .

Thus LHS for is:

.

.

Clearly except last two terms, it is equivalent to LHS of . Thus we can replace this with RHS of as is true. Thus we have:

.

Moving first term to the end:

.

On adding last two terms:

.

.

Clearly it is equivalent to RHS of . Thus LHS and RHS of are equal. Or is true.

Thus if is true then is also true.

**Soln9**

**(a)**

By Mathematical induction:

__Base Case:__

For . We have . Thus is true.

__Induction Step:__

Suppose is true. Thus for some integer , .

Thus we have for : .

Since , we get . Clearly for , is divisible by . Thus if is correct then is also correct.

**(b)**

By Mathematical induction:

__Base Case:__

For . We have . Thus is true.

__Induction Step:__

Suppose is true. Thus for some integer , .

Thus we have for : .

Since from part(a) is divisible by , it follows where is integer. Thus we have:

. Clearly is integer, thus is also true.

**Soln10**

By Mathematical induction:

__Base Case:__

For , we have . Thus is true.

__Induction Step:__

Suppose is true. Thus for some integer , . Thus . Thus for we have:

.

.

.

.

.

.

.

, where is an integer.

Thus is true.

**Soln11**

By Mathematical induction:

__Base Case:__

For , we have . Thus is true.

__Induction Step:__

Suppose is true. Thus for some integer , . Thus . Thus for we have:

.

.

.

.

.

.

, where is an integer.

Thus is true.

**Soln12**

By Mathematical induction:

__Base Case:__

For , we have . Thus is true.

__Induction Step:__

Suppose is true. Thus for some integer , .

Thus for we have:

.

.

.

.

, where is an integer.

Thus is true.

**Soln13**

By Mathematical induction:

__Base Case:__

For , we have . Thus is true.

__Induction Step:__

Suppose is true. Thus for some integer , .

Thus for we have:

.

.

.

.

.

.

, where is an integer.

Thus is true.

**Soln14**

By Mathematical induction:

__Base Case:__

For , we have . Thus is true.

__Induction Step:__

Suppose is true. Thus .

Thus for we have :

.

, since .

.

, since .

.

, since .

.

, since means .

.

Thus is true.

**Soln15**

By Mathematical induction:

__Base Case:__

For , we have . Thus . Thus is true.

__Induction Step:__

Suppose is true. Thus atleast one of the following is true:

- .
- .
- .

where are integers.

Now consider , we have following possible cases:

Case 1: .

Thus , or . Thus .

Case 2: .

Thus , or . Thus .

Case 3: .

Thus , or . Thus .

Thus from all cases, is also true.

**Soln16**

By Mathematical induction:

__Base Case:__

For , we have . Thus is true.

__Induction Step:__

Suppose is true. Thus .

Thus for we have .

, since is true.

.

.

.

Thus is also true.

**Soln17**

**(a)** Base case is not covered.

**(b)** It appears formulae should be .

By Mathematical induction:

__Base Case:__

For , we have . Thus is true.

__Induction Step:__

Suppose is true. Thus .

Thus for we have .
, since is true.

.

.

.

.

Thus is true.

**Soln18**

By Mathematical induction:

__Base Case:__

For . Thus is odd. So we have . Thus is true.

__Induction Step:__

Suppose is true. Thus if is odd, and if is even .

Thus for we have following cases:

Case 1: is odd.
Thus . Also since is true and is odd, . Since and

, it follows that . Thus . Since is odd, it follows is
even. Thus is true if is odd.

Case 2: is even.
Thus . Also since is true and is even, . Since and

, it follows that . Thus . Since is even, it follows is
odd. Thus is true if is even.

Thus is true for all possible cases.

**Soln19**

Suppose .

**(a)**

By Mathematical induction:

__Base Case:__

For . Thus and . Clearly from the give . Thus is true.

__Induction Step:__

Suppose is true. Thus .

Thus for we have :
.

, Since .

, Since .

.

Since is true, . Since , it follows . Thus .

Thus . It follows is true.

**(b)**

By definition of , we have . Thus we only need to prove .

Suppose and . We will prove this by contradiction. Suppose . Thus by part(a) we have . It follows . Thus . But it contradicts with the given that . Thus .

**(c)**

To Prove , which is equivalent to proving:

.

.

.

Since , . Also from part(a) , or . Since and , it follows . Thus is true.

**(d)**

By Mathematical induction:

__Base Case:__

For . Thus we have to prove , or , which on simplifying , or . Thus we need to prove . This is true as from part(c) for .

__Induction Step:__

Suppose is true. Thus .

Multiplying both sides by , we get:

.

.

.

Using part(c), , we get:

.

.

Since , we get:

.

Thus is true.