Principle of Mathematical Induction: Statement, Proof and Examples

The Principle of Mathematical Induction is a fundamental mathematical technique used to prove statements or formulas that are asserted to be true for all natural numbers. It is a powerful and elegant method that leverages the well-ordered nature of the set of natural numbers to establish the validity of an infinite sequence of propositions.

Principle of Mathematical Induction

Mathematical induction is one of the methods which can be used to prove a variety of mathematical statements which are formulated in terms of $n$, where $n$ is a positive integer (natural number)

Suppose there is a given statement P(n) involving the natural number n such that

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$.

Property (i) is simply a statement of fact. 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)$.

Property (ii) is a conditional property. It does not assert that the given statement is true for $n = k$, but only that if it is true for $n = k$, then should also be true for $ n = k +1$ for this principle to be applicable. So, to prove that the property holds, only prove that conditional proposition:

If the statement is true for $n = k$, then it is also true for $n = k + 1.$

Prove the statement:

$\mathrm{P}(\mathrm{n})=1+2+3+\ldots \ldots+\mathrm{n}=\frac{\mathrm{n}(\mathrm{n}+1)}{2}$ is true for all natural numbers.

Proof:

Step 1: Check if $P(1)$ is true
For $\mathrm{n}=1$, we have

$
\begin{array}{ll}
\mathrm{P}(1): & 1=\frac{1(1+1)}{2} \\
\Rightarrow & 1=1
\end{array}
$
So, formula is true for $n=1$.So $P(1)$ is true

Step 2: Assume $P(k)$ to be true and using that check if $P(k+1)$ is true
Suppose that $P(k)$ is true for some positive integer $k$

$
\mathrm{P}(\mathrm{k})=1+2+3+\ldots \ldots+\mathrm{k}=\frac{\mathrm{k}(\mathrm{k}+1)}{2}
$
Now we need to prove that $P(k+1)$ is also true.

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

we already have,

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

add $(k+1)$ both side in eq (i)

$
\begin{array}{ll}
\Rightarrow & 1+2+3+\ldots \ldots+(k+1)=\frac{\mathrm{k}(\mathrm{k}+1)}{2}+(\mathrm{k}+1) \\
\Rightarrow & 1+2+3+\ldots \ldots+(\mathrm{k}+1)=\frac{(\mathrm{k}+1)}{2}(\mathrm{k}+2)
\end{array}
$

Therefore, $P(k+1)$ is true and the inductive proof is now completed.
Hence $P(n)$ is true for all natural numbers $n$.

Solved Examples Based on Mathematical Induction:

Example 1: What can we deduce from the following mathematical expression? $x^2=9$
1) $x=3$
2) $x=\sqrt{9}$
3) $x= \pm 3$
4) Both (B) and (C)

Solution

Principle of Mathematical Induction -

Mathematical induction is one of the techniques which can be used to prove a variety of mathematical statements which are formulated in terms of $n$, where $n$ is a positive integer

Principle of Mathematical Induction

Principle of Mathematical Induction

$
\begin{aligned}
& x^2=9 \\
& \Rightarrow x^2-9=0 \Rightarrow(x-3)(x+3)=0
\end{aligned}
$
Thus $x= \pm 3$

Example 2: To prove a result by mathematical induction what values do we need to check for n ?
1) $n=1, n=k$
2) $n=1, n=k, n=k+1$
3) $n=1, n=k-1, n=k$
4) Both (B) and (C)

Solution

Principle of Mathematical Induction

Suppose there is a given statement $P(n)$ involving the natural number n such that
1. The statement is true for $n=1$, i.e., $P(1)$ is true, and
2. If the statement is true for $\mathrm{n}=\mathrm{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$.
Property (ii) is a conditional property. It does not assert that the given statement is true for $n=k$, but only that if it is true for $n=k$, then it is also true for $\mathrm{n}=\mathrm{k}+1$. So, to prove that the property holds, only prove that conditional proposition:

If the statement is true for $\mathrm{n}=\mathrm{k}$, then it is also true for $\mathrm{n}=\mathrm{k}+1$.
As long as the terms are consecutive like ( $k, k+1$ ) or ( $k-1, k)$, Principle of Mathematical Induction can be applied

So, both B and C options are correct

Example 3: The sum $\sum_{k=1}^n(1+2+3+4+\ldots+k)$ is a polynomial in $n$ of degree
1) 2
2) 3
3) 4
4) 5

Solution

$
\sum_{k=1}^n \frac{k^2+k}{2}=\frac{1}{2}\left(\sum k^2+\sum k\right)
$

which is a polynomial of degree 2

Example 4: The expression $15^4-7^4$ is divisible by
1) 3
2) 6
3) 9
4) 11

Solution
Principle of Mathematical Induction -

$
\begin{aligned}
& 15^4-7^4=(15+7)(15-7)\left(15^2+7^2\right) \\
& =22 * 8 *(225-49) \\
& =22 * 8 * 176
\end{aligned}
$
Since $\left(15^2+7^2\right)$ is divisible by 11

Example 5: The expression $7^{2 n}+2^{3 n-3} * 3^{n-1}$ is divisible by
1) $49$
2) $64$
3) $25$
4) $36$

Solution

Principle of Mathematical Induction

Mathematical induction is one of the techniques which can be used to prove a variety of mathematical statements which are formulated in terms of $n$, where n is a positive integer

For $\mathrm{n}=1,7^2+2^0 * 3^0=49+1=50$
It is divisible by 25
Let $\mathrm{P}(\mathrm{r})$ be true for $\mathrm{n}=\mathrm{r}$

$
7^{2 r}+2^{3 r-3} \cdot 3^{r-1}=25 k
$

For $\mathrm{n}=\mathrm{r}+1$,

$
\begin{aligned}
& \Rightarrow 49.7^{2 r}+2^{3 r} \cdot 3^r=49.7^{2 r}+8.2^{3 r-3} \cdot 3.3^{r-1} \\
& =49.7^{2 r}+24\left(25 k-7^{2 r}\right)_{(\text {From (i)) }} \\
& =25\left(7^{2 r}+24 k\right)
\end{aligned}
$

Summary
Mathematical induction is one of the techniques which can be used to prove a variety of mathematical statements which are formulated in terms of $n$, where n is a positive integer. The Principle of Mathematical Induction is a cornerstone of mathematical proof techniques, enabling the validation of infinite sequences of propositions. Its elegance lies in proving a universal truth by verifying a base case and a simple inductive step. The method's versatility extends across numerous mathematical domains, proving invaluable in establishing fundamental theorems and solving complex problems.