Principle of Mathematical Induction: Statement, Proof and Examples

Principle of Mathematical Induction

Mathematical induction is a method or technique used to prove a mathematical statement generalized for $n$ terms where $n$ is a natural number. For instance, let's consider the sum of odd numbers which is

$\begin{aligned} 1 & =1 \\ 1+3 & =4 \\ 1+3+5 & =9 \\ 1+3+5+7 & =16 \\ 1+3+5+7+9 & =25\end{aligned}$

From this, we could say that sum of 2 odd numbers is $4$ which is $2^2$, sum of 3 odd numbers is $9$ which is $3^2$, sum of 4 odd numbers is $16$ which is $4^2$, sum of 5 odd numbers is 25 which is $5^2$, and it goes on. From this, we could generalize the formula for the sum of odd numbers as $n^2$.

Now, let us state the principle of mathematical induction.

Principle of Mathematical Induction Class 11

The following result is also called the first principle of mathematical induction.

Let $P(n)$ be a mathematical statement where $n$ is a natural number.

1. The statement is true for $n = 1$, i.e., $P(1)$ is true, and

2. If the statement is true for $n = k$ (where $k$ is some positive integer), then the statement is also true for $n = k + 1$, i.e., truth of $P(k)$ implies the truth of $P (k + 1).$

Then, $P(n)$ is true for all natural numbers $n$.

1. This is the first step, typically a fact about the statement called the base step. Here, the mathematical statement is checked whether it is true for $n=1$(or any natural number). There may be situations when a statement is true for all $n ≥ 2$. In this case, step 1 will start from $n = 2$ and we shall verify the result for $n = 2$, i.e., $P(2)$.

2. In the second step, it is assumed that the statement is true for $n=k$ where $k$ is a positive integer. This process is called the inductive step. If the inductive step yields the result as true, then it is obvious that it is true for $n+1$. Hence, the statement is true for all natural numbers $n$.

Now, let's apply this principle of mathematical induction to our well known result, the sum of $n$ natural numbers.

Let $
P(n):=1+2+3+\cdots+n=\frac{n(n+1)}{2}
$

Substituting the value of $n=1$, in the statement we get, $P(1)=\frac{1(1+1)}{2}=1$. Hence, $P(1)$ is true.

Let us assume that the statement is true for $n=k$. Then

$
P(k)=1+2+3+\ldots+k=\frac{k(k+1)}{2}
$

We need to show that $P(k+1)$ is true. Consider,

$
P(k+1)=\underbrace{1+2+3+\cdots+k}+(k+1)=\frac{k(k+1)}{2}+(k+1) .
$

That is, $
P(k+1)=\frac{k(k+1)+2(k+1)}{2}=\frac{(k+1)(k+2)}{2}
$

This implies, $P(k+1)$ is true. According to principle of mathematical induction if p(k+1) is true, then it is true for all natural numbers. The validity of $P(k+1)$ follows from that of $P(k)$. Therefore by the principle of mathematical induction, for all integers $n \geq 1$, $
1+2+3+\cdots+n=\frac{n(n+1)}{2}
$

Principle of Mathematical Induction Proof

The principle of mathematical induction proof is direct and obvious. To check whether a statement is true for $n$ natural numbers, it is fundamental check whether it is true for $n=1$(or any other natural number). And If it is true for $n=k$, then it is important to check whether it is true for $n=k+1$.

After which every $k+1$ is considered as $k$ and further repeated. So, it can be generalized according to principle of mathematical induction if p(k+1) is true, then it is true for all $n$ natural numbers.

Second Principle of Mathematical Induction

Let $P(n)$ be a mathematical statement where $n$ is a natural number.

1. The statement is true for $n = 1$, i.e., $P(1)$ is true, and

2. If the statement is true for $n = 1$ to $k$ (where $k$ is some positive integer), then the statement is also true for $n = k + 1$, i.e., truth of $P(k)$ implies the truth of $P (k + 1).$

Then, $P(n)$ is true for all natural numbers $n$.

The difference between the first principle of mathematical induction and second principle of mathematical induction is that, in first principle of mathematical induction, the inductive step is assumed for $n=k$ while in second principle of mathematical induction, the inductive step is assumed for $n=1$(or any natural number used in base step) to $k$.

Now, let's look into second principle of mathematical induction examples.

Second Principle of Mathematical Induction Example

Every integer $n \geq 2$ is divisible by at least one prime number.

For $n=2, 2$ is a prime, so it is divisible by itself, which is a prime number.

Now, Assume that every integer $n$ from 2 to $k$ is divisible by at least one prime.

Now we can prove the statement for $n=k+1$ in two cases.

Case 1: If $k+1$ is prime, then it is divisible by itself, which is a prime.

Case 2: If $k+1$ is not prime, then it can be factored into two integers $a$ and $b$, where $1<a \leq$ $b<k+1$. By the inductive hypothesis, both $a$ and $b$ are divisible by primes. Therefore, $k+1=a \times b$ is divisible by a prime (either $a$ or $b$ ).

Thus, by second principle of mathematical induction, every integer $n \geq 2$ is divisible by at least one prime number.

Principle of Mathematical Induction Examples

Example 1: The smallest positive integer $n$, for which $n!<\left(\frac{n+1}{2}\right)^n$ hold is
1) $1$
2) $2$
3) $3$
4) $4$

Solution:

Let $P(n): \quad n!<\left(\frac{n+1}{2}\right)^n$

Step I: For $\mathrm{n}=2 \Rightarrow 2!<\left(\frac{2+1}{2}\right)^2 \Rightarrow 2<\frac{9}{4}$
$\Rightarrow \quad 2<2.25$ which is true. Therefore, $\mathrm{P}(2)$ is true.

Step II : Assume that $\mathrm{P}(\mathrm{K})$ is true, then $\mathrm{P}(\mathrm{K}): k!<\left(\frac{k+1}{2}\right)^k$

Step III : For $\mathrm{n}=\mathrm{k}+1, P(k+1):(k+1)!<\left(\frac{k+2}{2}\right)^{k+1}$

$\Rightarrow \quad k!<\left(\frac{k+1}{2}\right)^k \Rightarrow(k+1) k!<\frac{(k+1)^{k+1}}{2^k}$.

$\Rightarrow \quad(k+1)!<\frac{(k+1)^{k+1}}{2^k}$
and $\frac{(k+1)^{k+1}}{2^k}<\left(\frac{k+2}{2}\right)^{k+1}$

$\Rightarrow\left(\frac{k+2}{k+1}\right)^{k+1}>2 \Rightarrow\left[1+\frac{1}{k+1}\right]^{k+1}>2$

$\Rightarrow 1+(k+1) \frac{1}{k+1}+{ }^{k+1} C_2\left(\frac{1}{k+1}\right)^2+\ldots \ldots . .>2$

$
\Rightarrow 1+1+{ }^{k+1} C_2\left(\frac{1}{k+1}\right)^2+\ldots \ldots>2
$

Which is true, hence (ii) is true.
From (i) and (ii), $(k+1)!<\frac{(k+1)^{k+1}}{2^k}<\left(\frac{k+2}{2}\right)^{k+1}$

$
\Rightarrow \quad(k+1)!<\left(\frac{k+2}{2}\right)^{k+1}
$

Hence this is true. Hence by the principle of mathematical induction $P(n)$ is true for all $n$.

By checking options,

(a) For $\mathrm{n}=1,1$ ! $<\left(\frac{1+1}{2}\right)^1 \Rightarrow 1<1$ which is wrong

(b) For $\mathrm{n}=2,2$ ! $<\left(\frac{3}{2}\right)^2 \Rightarrow 2<\frac{9}{4}$ which is correct

(c) For $\mathrm{n}=3,3$ ! $<\left(\frac{3+1}{2}\right)^3 \Rightarrow 6<8$ which is correct.

(d) For $\mathrm{n}=4,4$ ! $<\left(\frac{4+1}{2}\right)^4 \Rightarrow 24<\left(\frac{5}{2}\right)^4$
$\Rightarrow 24<39.0625$ which is correct.

But the smallest positive integer n is 2. Hence, the answer is the option 2.

Exapmle 2: Let $S(n)=1+3+5+\ldots+(2 n-1)=3+n^2$. Then which of the following is true?
1) $S(2)$ is correct
2) $
S(k) \Rightarrow S(k+1)
$
3) $S(1)$ is correct
4) Principle of mathematical induction can be used to prove this formula

Solution:

$
S(n): 1+3+5+-----+(2 n-1)=3+n^2
$

Now,

$
S(1): 1=3+1
$

Which is NOT true
So, option C, D are wrong

$
S(2): 1+3=3+4
$

This is also wrong

Now,
Assuming $S(k)$ is true

$
1+3+5+-------+(2 k-1)=3+k^2
$

Then

$
\begin{aligned}
& S(k+1): 1+3+5+-----+(2 k-1)+(2 k+1) \\
& =\left(3+k^2\right)+(2 k+1) \quad \ldots . .(\text { using (i)) } \\
& =3+(k+1)^2
\end{aligned}
$

So, $S(k) \Rightarrow S(k+1)$

Example 3: By the principle of mathematical induction, prove that, for all integers $n \geq 1$,

$
1^2+2^2+3^2+\cdots+n^2=\frac{n(n+1)(2 n+1)}{6}
$

Solution:
Let,

$
P(n)=1^2+2^2+3^2+\cdots+n^2=\frac{n(n+1)(2 n+1)}{6} .
$

Substituting $n=1$ in the statement we get, $P(1)=\frac{1(1+1)(2(1)+1)}{6}=1$. Hence, $P(1)$ is true.
Let us assume that the statement is true for $n=k$. Then

$
P(k)=1^2+2^2+3^2+\cdots+k^2=\frac{k(k+1)(2 k+1)}{6} .
$

We need to show that $P(k+1)$ is true. Consider

$
\begin{aligned}
P(k+1) & =\underbrace{1^2+2^2+3^2+\cdots+k^2}+(k+1)^2 \\
& =P(k)+(k+1)^2 \\
& =\frac{k(k+1)(2 k+1)}{6}+(k+1)^2 \\
& =\frac{k(k+1)(2 k+1)+6(k+1)^2}{6} \\
& =\frac{(k+1)(k(2 k+1)+6(k+1))}{6} \\
& =\frac{(k+1)\left(2 k^2+7 k+6\right)}{6} \\
& =\frac{(k+1)[(k+2)(2 k+3)]}{6} \\
& =\frac{(k+1)[((k+1)+1)(2(k+1)+1)]}{6}
\end{aligned}
$

That is,

$
P(k+1)=\frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}
$

This implies, $P(k+1)$ is true. The validity of $P(k+1)$ follows from that of $P(k)$. Therefore by the principle of mathematical induction,

$
1^2+2^2+3^2+\cdots+n^2=\frac{n(n+1)(2 n+1)}{6}, \text { for all } n \geq 1
$

Example 4: Let $a$ and $b$ be positive integers. Which of the following statements is true for all positive integers $n$?
1) $
(a+b)^n>a^n+b^n
$

2) $
a^n+b^n>(a+b)^n
$

3) $
(a+b)^n=a^n+b^n
$

4) $
(a+b)^n<a^n+b^n
$

Solution:

We will use the principle of mathematical induction to solve this problem.
The base case is when $n=1$, then $(a+b)^1>a^1+b^1$ which is the correct value.
Therefore, $(a+b)^n>a^n+b^n$
is true for $\mathrm{n}=1$.Now, assume that the statement is true for some positive integer k .

$
(a+b)^k>a^k+b^k
$

We need to show that

$
(a+b)^{(k+1)}>a^{(k+1)}+b^{(k+1)}
$

Expanding the left-hand side using the binomial theorem,

$
\begin{aligned}
& (a+b)^{(k+1)}=(a+b)^k \times(a+b) \\
& (a+b)^{(k+1)}=\left(a^k+k a^{(k-1)} b+\ldots\right) \times(a+b) \\
& (a+b)^{(k+1)}=a^{(k+1)}+(k+1) a^k b+\ldots
\end{aligned}
$

Since $a$ and $b$ are positive and we know that,

$
k a^{(k-1)} b<a^k \text { and } k b^k<b^{(k+1)}
$

Therefore, we have:

$
\begin{aligned}
& (a+b)^{(k+1)}>a^{(k+1)}+(k+1) a^k b+k b^{(k+1)} \\
& (a+b)^{(k+1)}>a^{(k+1)}+b^{(k+1)}
\end{aligned}
$

Therefore, the statement is true for all positive integers $n$.
Hence, $(a+b)^n>a^n+b^n$
is true for all positive integers $n$.

Example 5: Which of the following statements is true for all positive integers $n$ ?
1) $
2^n>n^2
$

2) $
n^3<3^n
$

3) $
n!>2^n
$

4) $
n^2>2 n
$

Solution:

We will use the principle of mathematical induction to solve this problem.
For $n=1$, we have,

$
1^3=1<3^1=3
$

which is true.

Therefore,
$n^3<3^n$ is true for $n=1$.
Assume that the statement is true for some arbitrary positive integer k .

$
\therefore k^3<3^k
$

We need to prove that the statement is also true for $(k+1)$ i.e. $(k+1)^3<3^{(k+1)}$
Expanding $(k+1)^3$ we get:

$
(k+1)^3=k^3+3 k^2+3 k+1
$

Now, using the inductive hypothesis
$k^3<3^k$. we can say:

$
k^3+3 k^2+3 k+1<3^k+3 k^2+3 k+1
$

To prove that $(k+1)^3<3^{(k+1)}$ it suffices to show that

$
\begin{aligned}
& \text { i.e, } 3^k+3 k^2+3 k+1<3^{(k+1)} \\
& 3 k^2+3 k<2\left(3^k\right)-1
\end{aligned}
$

We can see that this inequality holds for all positive integers $k$.
Therefore, the inductive step is proved.
Hence, by the principle of mathematical induction, we can say that

$
n^3<3^n
$

for all positive integers n.