Mathematical induction is one of the main tools to prove various mathematical formulas, inequalities, and theorems. In this section, we will discuss the basic concept of mathematical induction.
Table of Contents
What is Mathematical Induction
Mathematical induction is a special technique to prove many mathematical statements usually related to the set of all natural numbers. The technique involves the following two steps.
(A) Check that the statement is true for the base case; usually for $n=1.$
(B) Let $k \geq 1$ be a natural number. Assuming the statement is true for $k$, show that it is true for $k+1.$
Then by mathematical induction, we can conclude that the given statement is true for all $n \geq 1.$
Therefore, it is time to learn what a mathematical statement stands for.
Mathematical Statement
The conclusion related to one or more mathematical relations arising from the observations is called a mathematical statement. The following are few examples of mathematical statements.
(i) The sum of consecutive $n$ natural numbers is $n(n+1)/2$
(ii) $2^n>n$ for all natural numbers
(iii) $n(n+1)$ is divisible by $3$ for all natural numbers $n \geq 2$
Note that the first two statements above are true, but the last one is false. (Take $n=7.$ Then $n(n+1)$ $=7(7+1)$ is not divisible by $3.$) Also, observe that the above statements are related to the set of all natural numbers
\[\mathbb{N}=\{1, 2, 3, 4, \cdots\}\]
As the statements depend only on $n,$ we usually denote a mathematical statement related to $\mathbb{N}$ by the symbol $P(n)$ or $S(n).$
For example, let $P(n)$ denote the sum of the first $n$ natural numbers. So
$P(2):=$ The sum of first $2$ natural numbers $=1+2$
$P(3):=$ The sum of first $3$ natural numbers $=1+2+3$
$P(4):=$ The sum of first $4$ natural numbers $=1+2+3+4;$ and so on.
Principle of Mathematical Induction
Let $n_0$ be a fixed natural number. Let $P(n)$ be a mathematical statement where $n \geq n_0.$ Suppose that the following are true:
Step I: (The base case) $P(n_0)$ is true.
Step II: (The inductive step or the induction step) Let $k \geq n_0$ be a natural number. $P(k)$ is true implies that $P(k+1)$ is also true.
Note that the assumption in step II is called the induction hypothesis or the inductive hypothesis.
Step III: (The conclusion) If the above two steps hold for the statement $P(n),$ then by mathematical induction $P(n)$ is true for all natural numbers $n \geq n_0.$
See the below examples to understand how to use mathematical induction to prove mathematical statements.
Solved Examples of Mathematical Induction
Problem 1: (proof of the sum of first n natural numbers formula by induction) Prove that
\[1+2+3+\cdots+n=\frac{n(n+1)}{2}\]
Solution:
Let $P(n)$ denote the statement $1+2+3+…+n$ $=\frac{n(n+1)}{2}.$
(Base case) Put $n=1.$ Note that $1=$ $\frac{1(1+1)}{2}.$ So $P(1)$ is true.
(Induction hypothesis) Assume that $P(k)$ is true. So we have $1+2+\cdots +k$ $=\frac{k(k+1)}{2}.$
(Induction step) To show $P(k+1)$ is true.
Now, $1+2+ \cdots +k +(k+1)$
$=(1+2+\cdots +k)+(k+1)$
$=\frac{k(k+1)}{2}+k+1,$ by induction hypothesis.
$=(k+1)[\frac{k}{2}+1]$
$=(k+1)[\frac{k+2}{2}]$
$=(k+1)[\frac{(k+1)+1}{2}]$
So we have shown that $1+2+ \cdots +k +(k+1)$ $=\frac{(k+1)(k+1+1)}{2}.$ It means that $P(k+1)$ is true. Hence we deduce that $P(k)$ implies that $P(k+1).$
Thus by mathematical induction, we conclude that $P(n)$ is true for all integers $n \geq 1.$ In other words, 1+2+…+n=n(n+1)/2 is proved.
