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.