Mathematics > Principle of Mathematical Induction

Add Comment Bookmark share + Refresher Material


Suppose there is a given statement  involving the natural number n such that

  1. The statement is true for n = 1, i.e.,  is true, and
  2. If the statement is true for n = k (where k is some positive integer), then the statement is also true for , i.e., truth of  implies the truth of Then,  is true for all natural numbers n.

 

Examples

Question

Prove that  for all positive integers n.

Solution

Let

When  Hence P(1) is true.

Assume that is true for any positive integers k, i.e.  ... (1)

We shall now prove that  is true whenever  is true.

Multiplying both sides of (1) by 2, we get 2.  i.e.,

Therefore,  is true when  is true. Hence, by principle of mathematical induction,  is true for every positive integer n.

 

Question

For every positive integer n, prove that  is divisible by 4.

Solution

 :  is divisible by 4.

We note that

: 71 – 31 = 4 which is divisible by 4. Thus  is true for n = 1

Let  be true for some natural number k,

i.e,:  is divisible by 4.

We can write  = 4d, where

Now, we wish to prove that  is true whenever  is true.

Now

=

=

From the last line, we see that  is divisible by 4. Thus,  is true when P(k) is true. Therefore, by principle of mathematical induction the statement is true for every positive integer n.

Comments Add Comment
Ask a Question