Mathematical Induction

Mathematical induction, is a technique for proving results or estabpshing 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 n^th 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 imes 3^k - 1 = (2 imes 3^k) + (3^k - 1)$

The first part $(2 imes 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$.