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: 13 +23 + 33 + ….. +n3 = (n(n+1) / 2)2, the statement is considered here as true for all the values of natural numbers.
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.
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.
Example 1: Prove that the sum of cubes of n natural numbers is equal to ( n(n+1)2)2 for all n natural numbers.
In the given statement we are asked to prove:
13+23+33+⋯+n3 = (n(n+1)2)2
Step 1: Now with the help of the principle of induction in math let us check the validity of the given statement P(n) for n=1.
P(1)=(1(1+1)2)2 = 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.,
13+23+33+⋯+k3= (k(k+1)2)2 .
Step 3: Let us now try to establish that P(k+1) is also true.
13+23+33+⋯+k3+(k+1)3 = (k(k+1)2)2+(k+1)3
Example 2: Show that 1 + 3 + 5 + … + (2n−1) = n2
Step 1: Result is true for n = 1
That is 1 = (1)2 (True)
Step 2: Assume that result is true for n = k
1 + 3 + 5 + … + (2k−1) = k2
Step 3: Check for n = k + 1
i.e. 1 + 3 + 5 + … + (2(k+1)−1) = (k+1)2
We can write the above equation as,
1 + 3 + 5 + … + (2k−1) + (2(k+1)−1) = (k+1)2
Using step 2 result, we get
k2 + (2(k+1)−1) = (k+1)2
k2 + 2k + 2 −1 = (k+1)2
k2 + 2k + 1 = (k+1)2
(k+1)2 = (k+1)2
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.