Principle of Mathematical Induction

Trigonometry

Trigonometry Logo

Principle of Mathematical Induction

Mathematical Induction is a technique of proving a statement, theorem or formula which is thought to be true, for each and every natural number n. By generalizing this in form of a principle which we would use to prove any mathematical statement is ‘Principle of Mathematical Induction‘.

For example: 13 +23 + 33 + ….. +n3 = (n(n+1) / 2)2, the statement is considered here as true for all the values of natural numbers.

Principle of Mathematical Induction Solution and Proof

Consider a statement P(n), where n is a natural number. Then to determine the validity of P(n) for every n, use the following principle:

Step 1:  Check whether the given statement is true for n = 1.

Step 2: Assume that given statement P(n) is also true for n = k, where k is any positive integer.

Step 3:  Prove that the result is true for P(k+1) for any positive integer k.

If the above-mentioned conditions are satisfied, then it can be concluded that P(n) is true for all n natural numbers.

Proof:

The first step of the principle is a factual statement and the second step is a conditional one. According to this if the given statement is true for some positive integer k only then it can be concluded that the statement P(n) is valid for n = k + 1.

This is also known as the inductive step and the assumption that P(n) is true for n=k is known as the inductive hypothesis.

Solved problems

Example 1: Prove that the sum of cubes of n natural numbers is equal to ( n(n+1)2)2 for all n natural numbers.

Solution:

In the given statement we are asked to prove:

13+23+33+⋯+n= (n(n+1)2)2

Step 1: Now with the help of the principle of induction in math let us check the validity of the given statement P(n) for n=1.

P(1)=(1(1+1)2)2 = 1 This is true.

Step 2: Now as the given statement is true for n=1 we shall move forward and try proving this for n=k, i.e.,

13+23+33+⋯+k3= (k(k+1)2)2 .

Step 3: Let us now try to establish that P(k+1) is also true.

                  13+23+33+⋯+k3+(k+1)3 = (k(k+1)2)2+(k+1)3

                 13+23+33+⋯+k3+(k+1)3=k2(k+1)4+(k+1)3

                 = k2(k+1)2+4((k+1)3)4

                 =(k+1)2(k2+4(k+1))4

                 =(k+1)2(k2+4k+4)4

                 = (k+1)2((k+2)2)4

                 =(k+1)2(k+1+1)2)4

                 =(k+1)2((k+1)+1)2)4

Example 2: Show that 1 + 3 + 5 + … + (2n−1) = n2

Solution

Step 1: Result is true for n = 1

That is 1 = (1)2  (True)

Step 2: Assume that result is true for n = k

1 + 3 + 5 + … + (2k−1) = k2 

Step 3:  Check for n = k + 1

i.e. 1 + 3 + 5 + … + (2(k+1)−1) = (k+1)2 

We can write the above equation as,

1 + 3 + 5 + … + (2k−1) + (2(k+1)−1) = (k+1)2

Using step 2 result, we get

k2 + (2(k+1)−1) = (k+1)2

k2 + 2k + 2 −1 = (k+1)2 

k2 + 2k + 1 = (k+1)2

(k+1)2 = (k+1)2 

L.H.S. and R.H.S. are same.

So the result is true for n =  k+1

By mathematical induction, the statement is true.

We see that the given statement is also true for n=k+1. Hence we can say that by the principle of mathematical induction this statement is valid for all natural numbers n.

Example 3: 

Show that 22n-1 is divisible by 3 using the principles of mathematical induction.

To prove: 22n-1 is divisible by 3

Assume that the given statement be P(k)

Thus, the statement can be written as P(k) = 22n-1 is divisible by 3, for every natural number

Step 1: In step 1, assume n= 1, so that the given statement can be written as

P(1) = 22(1)-1 =  4-1 = 3. So 3 is divisible by 3. (i.e.3/3 = 1)

Step 2: Now, assume that P(n) is true for all the natural number, say k

Hence, the given statement can be written as 

P(k) =  22k-1 is divisible by 3.

It means that 22k-1 = 3a (where a belongs to natural number)

Now, we need to prove the statement is true for n= k+1

Hence, 

P(k+1) = 22(k+1)-1 

P(k+1)= 22k+2-1

P(k+1)= 22k. 22 – 1

P(k+1)= (22k. 4)-1

P(k+1) =3.2k +(22k-1)

The above expression can be written as

P(k+1) =3.22k + 3a

Now, take 3 outside, we get

P(k+1) = 3(22k + a)= 3b, where “b” belongs to natural number

It is proved that p(k+1) holds true, whenever the statement P(k) is true.

Thus, 22n-1 is divisible by 3 is proved using the principles of mathematical induction

Practice problems

  1. Prove that 1 × 1! + 2 × 2! + 3 × 3! + … + n × n! = (n + 1)! – 1 for all natural numbers using the principles of mathematical induction.
  2. Prove that 4n – 1 is divisible by 3 using the principle of mathematical induction

Use the principles of mathematical induction to show that 2 + 4 + 6 + … + 2n = n2 + n, for all natural numbers

Frequently Asked Question on the Principle of Mathematical Induction

What is meant by mathematical induction?

Mathematical induction is defined as a method, which is used to establish results for the natural numbers. Generally, this method is used to prove the statement or theorem is true for all natural numbers

Write down the two steps involved in the principles of mathematical induction?

The two steps involved in proving the statement are:
Proving that the given statement holds true for the initial value. This is called the base step
In step 2, proving that the statement is true for the nth value, and also proving that true for the (n+1)th iteration also. This step is called the induction step

Why do we use mathematical induction?

Mathematical induction is typically used to prove that the given statement holds true for all the natural numbers.

What is meant by weak and strong induction?

In weak induction, it is assumed that only a particular statement holds true at the kth step. But in strong induction, the given statement holds true for all the steps from base to the kth step.

Mention three different types of mathematical induction

The different types of mathematical induction are:
First principle of mathematical induction
Second principle of mathematical induction
Second principle of mathematical induction (variation)

To know more about math visit BYJU’S – The Learning App and learn with ease by watching the interactive videos. We wish you Happy learning!