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.

## Principle of Mathematical Induction

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.

## Second Principle of Mathematical Induction

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.

## Mathematical Induction with Inequalities

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.

## Mathematical Induction Examples

### 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.