In mathematics, mathematical induction helps us to check whether a given statement is true or false for all natural numbers and is a technique through which we can prove any theorem. A mathematical relation(s) is called a mathematical statement. A statement concerning the natural number n is generally denoted by P(n).

For example, Consider the statement n(n + 1) is an even number.
This statement is denoted by P(n), supposing P(n) denotes "n(n + 1) is an even number" then
P(1) is 1(1 + 1) is an even number.
P(2) is 2(2 + 1) is an even number etc.
That is by giving particular values of n we get particular statements.

Let P(n) be a statement involving the natural numbers such that
1. P(1) is true.
2. P(k + 1) is true, whenever P(k) is true.
then P(n) is true for all natural numbers.
It consists of the following steps:

Step 1: Basic Step - Verify whether P(n) is true for n = 1.

Step 2: Induction Step - Assume P(n) to be true for some particular value of n say n = k, and prove that the result is true for n = k + 1. That is show that P(k + 1) is true.

Step 3: Conclusion Step - This completes the principle of mathematical induction conclude by saying by Principle of Mathematical Induction P(n) is true for all natural numbers n.
It is also known as Inductive hypothesis. Let P(n) be a proposition involving positive integers n. If
1. P(n) is true for n = 1 and n = 2 , and
2. If P(n) is true for some positive integer k and k + 1, then P(n) is also true for n = k + 2, then P(n) is true for all positive integers n.
We can solve any problem involving inequalities by mathematical induction.

Solved Example

Question: Prove by mathematical induction for any natural number n, $2^{n}>n$
Solution:
 
Let P(n) be the given statement.
P(n):  $2^{n}>n$ for any natural number.
Step 1: Let n = 1, then $2^{1}>1$     ==> 2 > 1 which is true. Therefore P(1) is true.

Step 2: Let P(n) be true for n = k( >1) 

$2^{k}>k$ (true)

We shall show that P(n) is true for n = k + 1.
Consider $2^{k+1} = 2^{k} * 2$
             $2^{k+1} > k * 2$                     ( $2^{k}$ > k)
             $2^{k+1} > (k + k)$                    ( It is written as k+k)
             $2^{k+1} > (k+1)$                           k > 1
             P(n) is true for n = k+1.
             P(k + 1) is true whenever P(k) is true.

Step 3: By Principle of Mathematical Induction P(n) is true for all natural integers n.
 


Solved Examples

Question 1: Using principle of mathematical induction prove $1^{3}+2^{3}+3^{3}+ ........... + n^{3}$ = $\frac{n^{2}(n+1)^{2}}{4}$
Solution:
 
Let P(n) be the given statement
P(n) = $1^{3}+2^{3}+3^{3}+ ........... + n^{3}$ = $\frac{n^{2}(n+1)^{2}}{4}$

Step -1 : Let n = 1, L.H.S = $1^{3}$ = 1,  R.H.S = $\frac{1^{2}(1+1)^{2}}{4}$ = 1
                 L.H.S = R.H.S   ==> P(1) is true.

Step -2 : Let P(n) be true for n = k
            $1^{3}+2^{3}+3^{3}+ ........... + k^{3}$ = $\frac{k^{2}(k+1)^{2}}{4}$         --------- 1

We shall prove that P(k + 1) is true.
Add $(k+1)^{3}$ to both sides of equation (1)

$1^{3}+2^{3}+3^{3}+ ........... + k^{3}+ (k+1)^{3}$ = $\frac{k^{2}(k+1)^{2}}{4}$ + $(k+1)^{3}$

= $\frac{k^{2}(k+1)^{2}+4(k+1)^{3}}{4}$

= $\frac{(k+1)^{2}(k^{2}+4k+4)}{4}$

= $\frac{(k+1)^{2}(k+2)^{2}}{4}$

Thus we have
$1^{3}+2^{3}+3^{3}+ ........... + k^{3}+ (k+1)^{3}$ = $\frac{(k+1)^{2}(k+2)^{2}}{4}$

This statement is same as P(n) where n = k + 1
The statement P(n) is true for n = k + 1.
Thus P(k + 1) is true whenever P(k) is true.

Step -3 : By Principle of Mathematical Induction P(n) is true for all natural integers.
 

Question 2: Prove by Mathematical Induction the sum of first n positive odd integers is $n^{2}$
Solution:
 
From the above given statement we have,
1 + 3 + 5 + 7+ .................. + (2n - 1) = $n^{2}$
Observe that (2n - 1) is the nth odd integer.
Let P(n) = 1 + 3 + 5 + 7+ .................. + (2n - 1) = $n^{2}$

Step -1 : Let n = 1, L.H.S = 1,    R.H.S = $1^{2}$ = 1
          L.H.S = R.H.S    ==>P(1) is true.

Step -2 : Let P(n) be true for n = k
1 + 3 + 5 + 7+ .................. + (2k - 1) = $k^{2}$      -----------1
We shall prove that P(k + 1) is true.
Adding both sides (2k + 1) in equation (1)

1 + 3 + 5 + 7+ .................. + (2k - 1) + (2k - 1) = $k^{2} + (2k +1) $

1 + 3 + 5 + 7 + .................. + (2k - 1) + (2k - 1)  = $(k + 1)^{2}$

This statement is same as P(n) where n = K + 1
The statement P(n) is true for n = k + 1.
Thus P(k + 1) is true whenever P(k) is true.

Step -3 : By Principle of Mathematical Induction P(n) is true for all natural integers.