Maths
Study Material

Principle of Mathematical Induction and Solved Examples

Principle of Mathematical Induction is used in several fields of mathematics to prove statements of the form P(n), n ∈ N. Let us learn about it.

4 minutes long
Posted by Tanwir Silar, 18/7/2021
Principle of Mathematical Induction and Solved Examples

Hesap Oluştur

Got stuck on homework? Get your step-by-step solutions from real tutors in minutes! 24/7. Unlimited.

TRY FOR FREE

 

Let us get familiar with the tool of mathematics which helps us to prove or disprove a statement of the form P(n), n ∈ N. that is Principle of Mathematical Induction.

What is an Inductive Step?

Before going through the formal definition of the concept, it is better to know about an inductive set. A set S is said to be an inductive set if 1∈ S and x + 1 ∈ S whenever x ∈ S. Since N is the smallest subset of R which is an inductive set, it follows that any subset of R that is an inductive set must contain N.

Generic solution approach

Having known about the inductive set, let us move forward by discussing the approach to solve a problem of Mathematical Induction. Suppose there is a given statement P(n) involving the natural number n such that

(i) The statement is true for n = 1, i.e., P(1) is true, and
(ii) If the statement is true for n = k (where k is some positive integer), then the statement is also true for n = k+1, i.e., truth of P(k) implies the truth of P(k+1).

Then, P(n) is true for all natural numbers n.

The second step of the approach is called the inductive hypothesis, while the first step is often referred as the basic step.

Solved Problems on Mathematical Induction

Example 1: For all n ≥ 1, prove that

Formula for sum of first n natural numbers

Solution: Let the given statement be P(n) i.e.,
Sum of squares of n natural numbers
Step 1: Prove that P(1) is true
For n = 1, Basic step of PMI, which is true.


Step 2: Assume that P(k) is true for some positive integer k i.e.,

Sum of squares of first k natural numbers

We shall now prove that P(k + 1) is also true. Now, we have

Solution of example 1 of mathematical induction

Thus P(k + 1) is true, whenever P(k) is true.
Hence, from the principle of mathematical induction, the statement P(n) is true for all natural numbers n.

Example 2: For every positive integer n, prove that 7n – 3n is divisible by 4.

Solution: We can write
P(n) : 7n – 3n is divisible by 4

Step 1:
We need to prove P(1) is true
P(1): 7 – 3 = 4 which is divisible by 4. Thus P(n) is true for n = 1
Step 2:
Let P(k) be true for some natural number k,
i.e., P(k) : 7k – 3k is divisible by 4.
We can write, 7k – 3k = 4d where d ∈ N.
As part of the induction hypothesis, we need to prove that P(k + 1) is true whenever P(k) is true.
Now, we can write P(k+1) as,
Main solution of example2
The above calculations show that 7(k+1) – 3(k+1) is divisible by 4. Thus, P(k+1) is true when P(k) is true.
Hence, from the principle of mathematical induction, the statement P(n) is true for all natural numbers n.

Any problem related to Principle of Mathematical Induction could be solved using the above approach.


Picked For You With Mathematical Induction


To solve and ask more and more questions download Kunduz app for free.

Fastest homework help from expert tutors

Got stuck on homework? Get your step-by-step solutions from real tutors in minutes! 24/7. Unlimited.

TRY FOR FREE