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: 1³ +2³ + 3³ + ….. +n³ = (n(n+1) / 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)² for all n natural numbers.

Solution:

In the given statement we are asked to prove:

1³+2³+3³+⋯+n³ = ( [n(n+1)]/2)²

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

P(1)=( [1(1+1)]/2)² = (2/2)² = 1² =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.,

1³+2³+3³+⋯+k³= ( [k(k+1)]/2)² .

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

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

Solution: 

Step 1: Result is true for n = 1

That is 1 = (1)²  (True)

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

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

Step 3:  Check for n = k + 1

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

We can write the above equation as,

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

Using step 2 result, we get

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

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

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

(k+1)² = (k+1)² 

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 2²ⁿ-1 is divisible by 3 using the principles of mathematical induction.

To prove: 2²ⁿ-1 is divisible by 3

Assume that the given statement be P(k)

Thus, the statement can be written as P(k) = 2²ⁿ-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) = 2²⁽¹⁾-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 numbers, say k

Hence, the given statement can be written as 

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

It means that 2^2k-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) = 2^2(k+1)-1 

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

P(k+1)= 2^2k. 2² – 1

P(k+1)= (2^2k. 4)-1

P(k+1) =3.^2k +(2^2k-1)

The above expression can be written as

P(k+1) =3.2^2k + 3a

Now, take 3 outside, we get

P(k+1) = 3(2^2k + 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, 2²ⁿ-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 4ⁿ – 1 is divisible by 3 using the principle of mathematical induction

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

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!