Principle of Mathematical Induction

The Principle of Mathematical Induction is a foundational concept in Mathematics, providing a rigorous method to prove statements true for all natural numbers. By establishing a base case and demonstrating the transition from one case to the next, mathematical induction offers a powerful tool for proving the validity of conjectures, theorems, and formulas across an infinite range of integers.

1.0Principle of Mathematical Induction Statement

Let P(n) represent a statement concerning the natural number n, satisfying the following conditions:

1. The statement holds true for n = 1, denoted as P (1) being true (or true for any specific natural number).
2. If the given statement is true for n = k (where k is any specific but arbitrary natural number), then it follows that the statement holds true for n = k + 1, indicating that the truth of P(k) leads to the truth of P (k + 1).

Under these conditions, P(n) holds true for all natural numbers n.

2.0Principle of Mathematical Induction Proof 

The Principle of Mathematical Induction is a fundamental concept in mathematics used to prove statements about natural numbers. It is typically used to prove statements of the form "P(n)" for all-natural numbers "n". The principle is usually divided into two steps:

1. Base Step: The first step is to prove that the statement is true for the base case, typically when "n = 1" or "n = 0", depending on the context. This establishes the foundation for the induction.
2. Inductive Step: The second step is to prove that if the statement is true for some arbitrary natural number "k", then it must also be true for the next natural number "k+1". This establishes the chain-like reasoning that extends the truth of the statement from the base case to all subsequent natural numbers.

Formally, the Principle of Mathematical Induction can be stated as follows:

Suppose "P(n)" is a statement involving a natural number "n".

1. Base Step: Prove that "P (1)" is true.
2. Inductive Step: Prove that for every natural number "k", if "P(k)" is true, then "P(k+1)" is also true.

By establishing the truth of the basis step and the inductive step, one can conclude that the statement "P(n)" holds true for every natural number "n".

The Principle of Mathematical Induction serves as a robust method for establishing the validity of statements, theorems, or formulas across all natural numbers. It generalizes the approach of proving truths for individual cases to encompass the entirety of the natural number set.

3.0Principle of Mathematical Induction Examples

Example 1: For all natural numbers n, n ≥1, Prove that 1 + 2 + 3 + … + n = $\frac{\mathrm{n}(\mathrm{n}+1)}{2}.$

Solution: Let's denote the given statement as P(n),

i.e. P(n): 1 + 2 + 3 + … + n = $\frac{\mathrm{n}(\mathrm{n}+1)}{2}$

Step 1:  For n = 1, 

P(1): $1=\frac{1(1+1)}{2}=\frac{1\times 2}{2}$=1

P (1) holds true.

Step 2: Assume that P (k) holds true for a certain positive integer k, 

i.e., 1 + 2 + 3 +. . . + k = $\frac{\mathrm{k}(\mathrm{k}+1)}{2}$

Step 3: Now, we will have to prove that P (k+1) is also true. We have 

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

Simplifying the right side of the equation:

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

$=\frac{{\mathrm{k}}^2+\mathrm{k}+2\mathrm{k}+1}{2}$

$=\frac{{\mathrm{k}}^2+3\mathrm{k}+1}{2}$

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

This confirms that the formula holds true for k + 1.

Since the formula holds for the base case (n = 1), and assuming it holds for K implies it holds for k +1, by the principle of mathematical induction, the formula is true for natural numbers.

Example 2. Prove that $2^n>n$

Solution : Let p(n): $2^n>n$

For n = 1, 2¹ > 1. Hence.  P (1) is true.

Assume that p(k) is true for any positive integer, i. e.

$2^k>k$                    ………. (1)

Now, we will have to prove that P (k+1) is also true. 

Multiplying both sides of (1) by 2, we get

$2.2k>2k$

i.e.,

$2k+1>2k$

= k + k > k + 1.

Therefore, p(k+1) holds true when p(k) holds true. Thus, in accordance with the principle of mathematical induction,  p(n) holds true for every positive integer n.

Example 3.  ${\sum }_{t=1}^{\mathrm{n}-1}\mathrm{t}(\mathrm{t}+1)=\frac{\mathrm{n}(\mathrm{n}-1)(\mathrm{n}+1)}{3}$, for all-natural number

Solution : We observe that-

L.H.S. = P (2) = ${\sum }_{t=1}^{2-1}\mathrm{t}(\mathrm{t}+1)={\sum }_{\mathrm{t}=1}^1\mathrm{t}(\mathrm{t}+1)1.2$

R.H.S. = $\frac{2(2-1)(2+1)}{3}\frac{2\cdot 1\cdot 3}{3}=1.2$

LHS = RHS.

Thus, P (n) holds true for n = 2.

Assume that P (n) is true for

i.e.  p(k) =  ${\sum }_{\mathrm{t}=1}^{\mathrm{k}-1}\mathrm{t}(\mathrm{t}+1)\frac{\mathrm{k}(\mathrm{k}-1)(\mathrm{k}+1)}{3}$

To prove that P (k+1) is true, we have-

${\sum }_{t=1}^{(k+1-1)}t(t+1)={\sum }_{t=1}^{k}t(t+1)$

$={\sum }_{\mathrm{t}=1}^{\mathrm{k}-1}\mathrm{t}(\mathrm{t}+1)+\mathrm{k}(\mathrm{k}+1)=\frac{\mathrm{k}(\mathrm{k}-1)(\mathrm{k}+1)}{3}+\mathrm{k}(\mathrm{k}+1)$

$=\mathrm{k}(\mathrm{k}+1)\left[\frac{\mathrm{k}-1+3}{3}\right]=\frac{\mathrm{k}(\mathrm{k}+1)(\mathrm{k}+2)}{3}$

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

Thus, P (k + 1) holds true, whenever P (k) holds true.

Thus, in accordance with the principle of mathematical induction, P(n) holds true for all-natural numbers n, n ≥ 2.

Example 4. Prove that 2^{2 n}-1 is divisible by 3.

Solution : The statement p(n) given as $p(n):2^{2n}-1$ is divisible by 3, for every natural number n.

We observe that P (1) is true, since.

2² –1 =4 –1 = 3 is divisible by 3.

Assume that p(n) is true for some natural number k, i.e., p(k): 2^2k – 1 is divisible by 3. i.e. 2^2k – 1 = 3q, where q $\in N$

Now, to prove that p (k+1) is true, we have.

P(k+1):  2^2(k+1) –1 = 2^2k+2 –1 = 2^2k. 2² –1 

$=2^{2\mathrm{k}}\cdot 4-1=3\cdot 2^{2\mathrm{k}}+\left(2^{2\mathrm{k}}-1\right)$

$=3.2^{2\mathrm{k}}+3\mathrm{q}=3\left(2^{2\mathrm{K}}+\mathrm{q}\right)=3\mathrm{m}\text{, }$where

Thus p(k+1) holds true, whenever p(k) holds true.

Thus, in accordance with the principle of mathematical induction, p (n) holds true for all-natural numbers n.

4.0Principle of Mathematical Induction Exercise 

Here are some practice questions based on the principle of mathematical induction. Prove the following by using the principle of mathematical induction.

Question 1: 4ⁿ –1 is divisible by 3, for each natural number n.

Question 2: 3²ⁿ – 1 is divisible by 8, for all natural numbers n.

Question 3: 2 + 4 + 6 . . . + 2n = n² + n, for all natural numbers n.

Question 4: For all prove that $\frac{1}{1.2}+\frac{1}{2.3}+\frac{1}{3.4}+\dots +\frac{1}{n(n+1)}=\frac{n}{n+1}$

5.0Solved question for Principle of Mathematical Induction

Q. Can you give an example of the Principle of Mathematical Induction proof?

Ans: An example is proving the formula for the sum of the initial n natural numbers: 1 + 2 + 3 + … + n =  $\frac{\mathrm{n}(\mathrm{n}+1)}{2}.$