Principle of Mathematical Induction: Statement, Proof and Examples

The principle of mathematical induciton is one of the important topics in pure and applied mathematics. The principle of mathematical induction is an interesting method of proof in Mathematics. The principle of mathematical induction is used to prove a mathematical statement for all possible cases. It has applications in pure and all branches of mathematics.

This article is about the concept of Principle of Mathematical Induction class 11 Principle of Mahthematical Induction chapter is not only essential for board exams but also for competitive exams like the Joint Entrance Examination (JEE Main), and other entrance exams such as SRMJEE, BITSAT, WBJEE, VITEEE, BCECE, and more.

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.