Mathematical Induction
Mathematical induction, is a technique for proving results or establishing statements for natural numbers. This part illustrates the method through a variety of examples.
Definition
Mathematical Induction is a mathematical technique which is used to prove a statement, a formula or a theorem is true for every natural number.
The technique involves two steps to prove a statement, as stated below −
Step 1(Base step) − It proves that a statement is true for the initial value.
Step 2(Inductive step) − It proves that if the statement is true for the nth iteration (or number n), then it is also true for (n+1)th iteration ( or number n+1).
How to Do It
Step 1 − Consider an initial value for which the statement is true. It is to be shown that the statement is true for n = initial value.
Step 2 − Assume the statement is true for any value of n = k. Then prove the statement is true for n = k+1. We actually break n = k+1 into two parts, one part is n = k (which is already proved) and try to prove the other part.
Problem 1
$3^n-1$ is a multiple of 2 for n = 1, 2, ...
Solution
Step 1 − For $n = 1, 3^1-1 = 3-1 = 2$ which is a multiple of 2
Step 2 − Let us assume $3^n-1$ is true for $n=k$, Hence, $3^k -1$ is true (It is an assumption)
We have to prove that $3^{k+1}-1$ is also a multiple of 2
$3^{k+1} - 1 = 3 \times 3^k - 1 = (2 \times 3^k) + (3^k - 1)$
The first part $(2 \times 3k)$ is certain to be a multiple of 2 and the second part $(3k -1)$ is also true as our previous assumption.
Hence, $3^{k+1} – 1$ is a multiple of 2.
So, it is proved that $3^n – 1$ is a multiple of 2.
Problem 2
$1 + 3 + 5 + ... + (2n-1) = n^2$ for $n = 1, 2, \dots $
Solution
Step 1 − For $n=1, 1 = 1^2$, Hence, step 1 is satisfied.
Step 2 − Let us assume the statement is true for $n=k$.
Hence, $1 + 3 + 5 + \dots + (2k-1) = k^2$ is true (It is an assumption)
We have to prove that $1 + 3 + 5 + ... + (2(k+1)-1) = (k+1)^2$ also holds
$1 + 3 + 5 + \dots + (2(k+1) - 1)$
$= 1 + 3 + 5 + \dots + (2k+2 - 1)$
$= 1 + 3 + 5 + \dots + (2k + 1)$
$= 1 + 3 + 5 + \dots + (2k - 1) + (2k + 1)$
$= k^2 + (2k + 1)$
$= (k + 1)^2$
So, $1 + 3 + 5 + \dots + (2(k+1) - 1) = (k+1)^2$ hold which satisfies the step 2.
Hence, $1 + 3 + 5 + \dots + (2n - 1) = n^2$ is proved.
Problem 3
Prove that $(ab)^n = a^nb^n$ is true for every natural number $n$
Solution
Step 1 − For $n=1, (ab)^1 = a^1b^1 = ab$, Hence, step 1 is satisfied.
Step 2 − Let us assume the statement is true for $n=k$, Hence, $(ab)^k = a^kb^k$ is true (It is an assumption).
We have to prove that $(ab)^{k+1} = a^{k+1}b^{k+1}$ also hold
Given, $(ab)^k = a^k b^k$
Or, $(ab)^k (ab) = (a^k b^k ) (ab)$ [Multiplying both side by 'ab']
Or, $(ab)^{k+1} = (aa^k) ( bb^k)$
Or, $(ab)^{k+1} = (a^{k+1}b^{k+1})$
Hence, step 2 is proved.
So, $(ab)^n = a^nb^n$ is true for every natural number n.
Strong Induction
Strong Induction is another form of mathematical induction. Through this induction technique, we can prove that a propositional function, $P(n)$ is true for all positive integers, $n$, using the following steps −
Step 1(Base step) − It proves that the initial proposition $P(1)$ true.
Step 2(Inductive step) − It proves that the conditional statement $[P(1) \land P(2) \land P(3) \land \dots \land P(k)] → P(k + 1)$ is true for positive integers $k$.
