Sales Toll Free No: 1-855-666-7446

# Mathematical Induction

Top
 Sub Topics In mathematical induction, we find whether a given statement is true for all the natural numbers or not. It is basically a technique used to prove a statement or a theorem, or a formula that is advanced about all natural numbers. The simplest form of mathematical induction is to identify that whether a statement which include a natural number 'n' holds for all values of n is true or not. A statement concerning the natural number n is generally denoted by P(n).Consider an example, 1 + 2 + 3 + …… + n = $\frac{n (n + 1)} {2}$. The value of P(n) gives a formula for finding the sum of the natural numbers which is less than or equal to number 'n'. Let the value of n be 0. Then, substituting the value of 'n' in $\frac{n (n + 1)} {2}$, we getP(1) =$\frac{1(1 + 1)}{2}$ = 1. So, we get the value of left and right hand side same. So, we can say mathematical induction is a mathematical process which is used to establish the validity of general result involving natural numbers. A mathematical relation is called a mathematical statement.

## 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 'n'.
This method of proof of a proposition P(n) by mathematical induction consists of the following steps:

Basic step: Verify the proposition P(n) for n = 1.

Induction step: Assume the proposition 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.

Conclusion step: This completes the principle of induction. Conclude by saying, "By principle of mathematical induction, P(n) is true for all natural number 'n'".

## Second Principle of Mathematical Induction

Second Principle of Mathematical Induction is a strong mathematical induction. Let j be an integer, and let T(n) be a predicate whose universe of discourse is the set of integers {j, j + 1, j + 2, ....}.
Assume that
1. T(j), and
2. T(j) for j $\leq$ i $\leq$ n implies P(n + 1). Then, T(n) is true $\forall$ n.
There is a difference between second principle and first principle only in the form of the induction hypothesis. In second induction, we assume not just T(n), but T(i) for all the integers i between j and n. We can use this assumption to show that T(n + 1).

The second principle of induction is also known as strong mathematical induction.

## Proof of Mathematical Induction

The proof of Mathematical Induction contains two steps, and the steps are shown below:

1. The basic case of induction mathematical is used to show that the statement holds the value of n is equal to the lowest value of n. Generally, we take the value of n as 0 or 1.
2. The inductive case of mathematical induction is used to show that the given statement holds the value of n. Then, the full statement also holds, when the value of n is substituted to n + 1.
This given method is applicable by proving the statement is true for the starting value. Then, we have to prove the process which is used to go from one value to the other value which is valid. If both the given values are taken, then any value can be calculated by performing the process

## Mathematical Induction Steps

To solve any problem by mathematical induction method, we have to follow some basic steps so that, we can easily find the solution of the problem.

The steps for mathematical induction are as follows:
1. For any given theorem, first we have to show that the given condition is true for n = 1.
2. Assume that it is true for n = k.
3. Explain that result is true for n = k + 1
4. Conclusion: Given statement is true for all values of n $\geq$ 1.

## Mathematical Induction Inequality

If ‘<, >,$\geq$, $\leq$ ' symbols are present in an expression, we say expression contains an inequality. Mathematical induction inequality can be understood with help of an example as follows:

### Solved Example

Question: Prove by the principle of mathematical induction $n^{2} \geq 2n$, where n = 2, 3, 4 and so on.
Solution:
Let the given statement be P(n).

Step 1: Let n = 2, L.H.S = $2^{2}$ = 4,
R.H.S = 2 x 2  =4
$\therefore$ L.H.S = R.H.S $\Rightarrow$ P(2) is true.

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

Step 3: We shall show that P(k + 1) is true.
Let n = k + 1. Then, $(k + 1)^{2}$ $\geq 2(k + 1)$ for every (k + 1) = 2, 3, 4 and so on.
$(k + 1) ^{2} = k^{2} + 1 + 2k$
$\geq 2k + 1 + 2k$  (Using step 1)
= $2k+ (1 + 2k)$
$\geq 2k + 2$

Thus, we have $(k + 1)^{2} \geq 2(k + 1)$
This statement is same as P(n), when n = k + 1
This shows that P(n) is true for n = k + 1.
Thus, P(k + 1) is true whenever P(k) is true.

Step 4: By principle of mathematical induction, P(n) is true for all natural number 'n'.

## Mathematical Induction Problems

Given below are some of the example in mathematical induction.

### Solved Examples

Question 1: Prove by the principle of mathematical induction
$1^{2}$ +$2^{2}$ +.........+ $n^{2}$ = $\frac{n(n+1)(2n+1)}{6}$ for all positive integer n.
Solution:
Let the given statement be P(n).

Step 1:
Let n = 1, L.H.S = 1$^{2}$ = 1, R.H.S =  $\frac{1(1+1)(2+1)}{6}$

=$\frac{6}{6}$ = 1

$\therefore$ L.H.S = R.H.S $\Rightarrow$ P(1) is true.

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

$1^{2}$ + $2^{2}$ +.........+$k^{2}$  = $\frac{k(k+1)(2k+1)}{6}$   ----1

Step 3: we shall show that P (k + 1) is true.
Adding both sides with (k+1)$^{2}$, we get
$1^{2}$ + $2^{2}$ +.........+$k^{2}$ + $(k+1)^{2}$

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

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

= $\frac{(k+1)[k(2k+1)+6(k+1)]}{6}$

=$\frac{(k+1)[2k^{2}+7k+6]}{6}$

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

=$\frac{(k+1)(k+2)[2(k+1)+1]}{6}$

Thus, we have, $1^{2}$ +$2^{2}$ +.........+$k^{2}$+ $(k+1)^{2}$ = $\frac{(k+1)(k+2)[2(k+1)+1]}{6}$

This statement is same as P(n), when n = k + 1
This shows that P(n) is true for n = k + 1.
Thus, P(k + 1) is true, whenever P(k) is true.

Step 4: By principle of mathematical induction, P(n) is true for all natural number 'n'.

Question 2: $\frac{1}{1.2}$ + $\frac{1}{2.3}$ + $\frac{1}{3.4}$ +.....+ $\frac{1}{n.(n+1)}$ =$\frac{n}{n+1}$ for all positive integer n.
Solution:
Let the given statement be P(n).

P(n) = $\frac{1}{1.2}$ + $\frac{1}{2.3}$ + $\frac{1}{3.4}$+.......+ $\frac{1}{n.(n+1)}$=$\frac{n}{n+1}$

Step 1:  Let n = 1, L.H.S = $\frac{1}{1. 2}$ = $\frac{1}{2}$

R.H.S = $\frac{1}{1+1}$ = $\frac{1}{2}$

L.H.S = R.H.S $\Rightarrow$ P(1)is true.

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

$\frac{1}{1.2}$ + $\frac{1}{2.3}$ + $\frac{1}{3.4}$ +.....+$\frac{1}{k(k+1)}$ = $\frac{k}{k+1}$    ....1

Step 3: We shall show that P(n) is true for n = k + 1.
Adding both sides of (1) with $\frac{1}{(k+1)(k+2)}$, we get

$\frac{1}{1.2}$ + $\frac{1}{2.3}$ +$\frac{1}{3.4}$ +.....+$\frac{1}{k(k+1)}$ +$\frac{1}{(k+1)(k+2)}$ = $\frac{k}{k+1}$ +$\frac{1}{(k+1)(k+2)}$

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

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

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

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

Thus, we have
$\frac{1}{1.2}$ + $\frac{1}{2.3}$ +$\frac{1}{3.4}$ +.....+$\frac{1}{k(k+1)}$ +$\frac{1}{(k+1)(k+2)}$ = $\frac{(k+1)}{(k+2)}$

This statement is same as P(n), when n = k + 1.
This shows that P(n) is true for n = k + 1.
Thus, P(k + 1) is true whenever P(k) is true.

Step 4: By principle of mathematical induction, P(n) is true for all natural number 'n'.