Introduction
Mathematical Induction is a methodology for proving natural-number conclusions, a formula or existing theorems.
There are 2 steps involved in order to prove these statements using Induction:
Step 1(Base step) :
Consider a starting point for the assertion to be true. It will always be true must prove that the statement is correct when n = starting value.
Mathematically:
Let n0 be a fixed integer. Suppose T (n) is a statement involving the natural number n, and we wish to prove that P (n) is valid for all n ≥ n0.
T (n0) is true i.e. T (n) is true for n = n0.
Step 2(Induction Step) :
Assuming the statement to be true for any value of n = k. Then prove that the statement is true for n = k+1.
Mathematically:
Let n0 be a fixed integer. Suppose T (n) is a statement involving the natural number n and we wish to prove that P (n) is true for all N ≥ n0.
Assume that the P (k) is true for n = k.
Then P (K+1) should also be true.
Examples
- Use the Principle of Mathematical Induction to verify that, for n any positive integer, 6n-1 is divisible by 5.
Solution:
For any n ≥ 1, let Pn be the statement that 6n − 1 is divisible by 5.
Base Case: The statement P1 says that
6 1 − 1 = 6 − 1 = 5 Eq No. 1
is divisible by 5, which is true.
Inductive Step: Fix k ≥ 1, and suppose that Pk holds, that is, 6k − 1 is divisible by 5.
It remains to show that Pk+1 holds, that is, that 6k+1 − 1 is divisible by 5.
6 k+1 − 1 = 6(6k ) − 1
= 6(6k − 1) − 1 + 6 From Eq. No-1
= 6(6k − 1) + 5
By Pk, the first term 6(6k − 1) is divisible by 5, the second term is divisible by 5.
Therefore the left-hand side is also divisible by 5.
Therefore Pk+1 holds.
Thus, P(n) holds true by the principle of mathematical Induction, for all n ≥ 1.
2. Verify the following mathematical equation using Mathematical Induction:
1 + 3 + 5 + ··· + 2n − 1 = n2
Solution:
Base Step: We are going to prove P(1).
LHS of P(1) = 1
= 12
= RHS of P(1).
So P(1) is true.
Inductive Step: Now, we’ll prove that for any natural number k, “if P(k) is true then P(k +1) is true.” So assume P(k) is true, i.e.
1+3+5+ ··· + 2k − 1 = k2
Therefore for P(k + 1):
LHS of P(k + 1) = 1 + 3 + 5 + ··· + 2k − 1 + 2(k + 1) − 1
= (LHS of P(k)) + 2(k + 1) − 1
= (RHS of P(k)) + 2k + 1 (by inductive assumption)
= k2 + 2k +1
= (k + 1)2
= RHS of P(k + 1)
So P(k + 1) is true, if P(k) is true.
Hence, by induction P(n) is true for all natural numbers