Method of Mathematical Induction: Principle, Applications, Solved Examples

Method of Mathematical Induction: Mathematical induction is a method of mathematical proof that is used to establish that any given statement is true for all natural numbers \(n.\) The method can also be used to extend the proof of statements for more general well-founded structures, such as trees; this generalisation, known as structural induction, is used in logic and computer science.

The validity of mathematical induction is logically equivalent to the well-ordering principle. In mathematical induction, we can prove any statement is true for any natural number in just three steps, and we can conclude the statement in general.

Types of Reasoning

In a mathematical discussion, two basic reasoning processes are commonly used for drawing scientific conclusions. 

1. Deduction
2. Induction 

Process of Deduction

The process used to conclude (or deduce) a particular result from a general result is called deduction.

Example: All the integers whose digit in unit place is \(0\) or \(5\) are divisible by \(5.\)

This is a general statement. Since \(365\) is an integer whose digit in unit place is \(5, 365\) is divisible by \(5.\) This is a particular statement. Here, from a general statement, we have concluded a particular statement.

Learn About Algebraic Expressions Here

Process of Induction

The reasoning process from a particular result to a general result is called induction.

Example: \(44\) is divisible by \(2.\) Hence, all integers ending with \(4\) are divisible by \(2.\)

Here, from a particular statement, we are drawing a general conclusion. This conclusion is nothing but a conjecture or guesswork, for we could have arrived at any other conclusion too.

For example, we could say that \(44\) is divisible by \(2.\) Also, \(44\) has two digits. Therefore, all two-digit integers are divisible by \(2\) is a false conclusion. For example, \(53\) is a two-digit integer, but it is not divisible by \(2.\)

Induction vs Deduction

In the process of induction, we make a tentative guess. This guess may be accurate. This truth must be proved by proper mathematical reasoning. Otherwise, it is declared false. This must be shown by providing a counter-example where the guess does not hold.

Unless it is mathematically proved, the conjecture remains a conjecture, no matter how many examples we may illustrate to support it. Thus, in mathematical induction, we first arrive at a conjecture and then go on to prove it.

How to Prove a Conjecture?

To prove a conjecture that is in the form of a statement, say \(P(n),\) involving natural numbers, we use the principle of mathematical induction.

Let us learn more about the method of principle induction in this article.

Principle of Mathematical Induction

From the arithmetic progression, we know that: 

Sum of \(n\) natural numbers\( = \frac{{n(n + 1)}}{2}.\) Hence, 

• Sum of first \(1\) natural number\( = 1 = \frac{{1(1 + 1)}}{2}\)
• Sum of first \(2\) natural numbers\( = 1 + 2 = 3 = \frac{{2(2 + 1)}}{2}\)
• Sum of first \(3\) natural numbers sum\( = 1 + 2 + 3 = 6 = \frac{{3(3 + 1)}}{2}\)

We have seen that the given formula holds for the first three natural numbers, i.e. it will be true for the first four natural numbers too.

We can write this as \(1 + 2 + 3 + 4 + \cdots + n = \frac{{n(n + 1)}}{2}\)

To verify the statement, we can substitute any positive integer for \(n\) and prove it. But this will not prove the statement in general for \(n.\)

For making it true for all values of n we have to make a chain reaction that will affect if any formula is true for some particular positive integer. Then, it should be automatically true for the next positive integer and the next indefinitely. 

Such conclusions may be produced by the method of mathematical induction.

Definition of Mathematical Induction

If \(P(n)\) is a statement involving a natural number \(n,\) such that

1. If \(P(1)\) is true, i.e. the statement is true for \(n=1\)
2. If \(P(k+1)\) is true whenever \(P(k)\) is true, i.e., the truth of \(P(k)\) implies the truth of \(P(k+1)\) then \(P(n)\) is true for all natural number \(n.\)

Method to Solve Mathematical Induction

Thus, to prove a statement \(P(n)\) to be true for all natural numbers, we have to follow the working rule:

• Step 1: Prove that \(P(1)\) is true: i.e., \(P(n)\) is true for \(n=1\)
• Step 2: Assume \(P(k)\) to be true; i.e., \(P(n)\) is true for \(n=k\)
• Step 3: Prove that \(P(k+1)\) is also true; i.e. \(P(n)\) is also true for \(n=k+1.\)

Hence, \(p(n)\) is true for all natural numbers \(n.\)

The method of induction is a strong and helpful device to prove theorems. A proof by induction is like climbing a ladder that has an infinite number of steps. While climbing a ladder, first, we have to climb the first step, then climb the second one, and so on until the \({n^{{\rm{th}}}}\) step is climbed. In a similar manner, to prove any statement by mathematical induction, first, we show it to be true for \(n=1,\) and then show it is hold for \(n=k + 1\) by assuming it is true for \(n = k.\) Hence say that the statement is also true for all natural numbers \(n.\)

Applications of Mathematical Induction in Real Life

There are several real-life uses of mathematical induction, and a few of them are listed below:

1. Domino Effect
   A domino effect, also known as a chain reaction, is the cumulative effect produced when one of the events sets off a chain of similar events.
2. Family Tree
   This shows the number of offspring in each generation. To generalise this, we use mathematical induction.

Solved Examples

Q1. Using mathematical induction, show that the sum of first \(n\) odd natural numbers is \({n^2}.\)
Sol:

 Let \(P(n):1 + 3 + 5 + \ldots + (2n – 1) = {n^2}…….\left( i \right)\)

Put \(n=1\) in \((i),\) we get,

\(P(1):1 = {1^2},\) which is true.

Let us assume that \(P(k)\) is true for any natural number \(k.\)

i.e., \(P(k):1 + 3 + 5 + \ldots + (2k – 1) = {k^2}………\left( {ii} \right)\)

Now we shall prove that \(P(k+1)\) is also true

\(P(k + 1):1 + 3 + 5 + \ldots + (2k – 1) + [2(k + 1) – 1] = {(k + 1)^2}\)

[By changing \(k\) to \(k\)+1 in \((ii)\)]

\( \Rightarrow P(k + 1):1 + 3 + 5 + \ldots + (2k – 1) + (2k + 1) = {(k + 1)^2}……..\left( {iii} \right)\)

L.H.S. of \((iii) = [(1 + 3 + 5 + \ldots + (2k – 1)] + (2k + 1)\)

\( = \left( {{k^2}} \right) + (2k + 1)\) [ using \((ii)\)]

\( = {(k + 1)^2} = \)R.H.S. of (iii)

Thus, \(P(k+1)\) is true whenever \(P(k)\) is true.

Hence, using the principle of mathematical induction, \(P(n)\) is true for all natural numbers \(n.\) Therefore, the sum of first \(n\) odd natural numbers is \({n^2}.\)

Q2. Prove that \({3^{(2n + 2)}} – 8n – 9\) is divisible by \(64.\)
Sol: Let \(P(n):{3^{2n + 2}} – 8n – 9\) is divisible by \(64…….\left( i \right)\)

When \(n=1,\)

\(P(1):{3^4} – 8.1 – 9 = 64,\) which is divisible by \(64\)

Let us assume that \(P(k)\) is true for any natural number \(k\)

i.e., \(P(k):{3^{2k + 2}} – 8k – 9\) is divisible by \(64\)

\( \Rightarrow {3^{2k + 2}} – 8k – 9 = 64m\) where \(m \in Z……..\left( {ii} \right)\)

Now we shall prove that \(P(k+1)\) is also true

i.e., \(P(k + 1):{3^{2(k + 1) + 2}} – 8(k + 1) – 9\) is divisible by \(64\) 

[ By changing \(n\) by \(k+1\) in \((i)\)]

Now, \({3^{2(k + 1) + 2}} – 8(k + 1) – 9 = {3^2} \cdot {3^{2k + 2}} – 8k – 17\)

\( = 9 \cdot {3^{2k + 2}} – 8k – 17\)

\( = 9 \cdot (64m + 8k + 9) – 8k – 17\)

[from \(\left( {ii} \right){3^{2k + 2}} = 64\,m + 8k + 9\)]

\( = 9 \cdot 64m + 72k + 81 – 8k – 17\)

\( = 9 \cdot 64m + 64k + 64\)

\(=64 \cdot (9m+k+1)\) is divisible by \(64.\) Thus, \(P(k+1)\) is true whenever \(P(k)\) is true.

Hence, using the principle of mathematical induction, \(P(n)\) is true for all natural numbers n, i.e. \({3^{2n + 2}} – 8n – 9\) is divisible by \(64,n \in N\).

Q3. Using the principle of mathematical induction, prove that \({x^n} – {y^n}\) is divisible by \((x−y)\), where \(x−y≠0\)
Sol: Let \(P(n):{x^n} – {y^n}\) is divisible by \(x−y,\) where \(x−y≠0…(i)\)

When \(n = 1,P(1):{x^1} – {y^1} = x – y,\) it is divisible by \((x−y)\)

\(∴P(1)\) is true.

Let us assume that \(P(k)\) is true for any natural number \(k\)

I.e., \(P(k):{x^k} – {y^k}\) is divisible by \((x−y)\)

\(\therefore {x^k} – {y^k} = m(x – y)\) for some integer \(m\)

\( \Rightarrow x = m(x – y) + {y^k}……….\left( {ii} \right)\)

Now, we shall prove that \(P(k+1)\) is also true 

i.e., \(P(k + 1):{x^{k + 1}} – {y^{k + 1}}\) is divisible by \(x−y\)

Now, \({x^{k + 1}} – {y^{k + 1}} = x \cdot {x^k} – y \cdot {y^k} = x\left[ {m(x – y) + {y^k}} \right] – y{y^k}\)      [Using \((ii)\)]

\( = mx(x – y) + x{y^k} – y{y^k}\)

\( = mx(x – y) + {y^k}(x – y)\)

\( = (x – y)\left[ {mx + {y^k}} \right]\)

This is divisible by \((x−y).\)

Thus, \(P(k+1)\) is true whenever \(P(k)\) is true. Hence, we can say that \(P(n)\) is true for all natural numbers \(n\) by the principle of mathematical induction.

i.e., \({x^n} – {y^n}\) is divisible by \((x−y),\) where \(x−y≠0.\)

Q4. Show that \({1^2} + {2^2} + {3^2} + {4^2} + \cdots {n^2} = \frac{{[n(n + 1)(2n + 1)]}}{6}\forall n \in N\)
Sol: Let \(P(n):{1^2} + {2^2} + {3^2} + {4^2} + \cdots {n^2} = \frac{{[n(n + 1)(2n + 1)]}}{6}\)

When \(n = 1,P(1):1 = \frac{{1(2)(3)}}{6} = 1\) is true.

Assume \(P(k)\) is true for some natural number \(k.\)

\(P(k):{1^2} + {2^2} + {3^2} + {4^2} + \cdots {k^2} = \frac{{[k(k + 1)(2k + 1)]}}{6}\)

We shall now prove that \(P(k+1)\) is also true.

Now, we have

L.H.S.\( = {1^2} + {2^2} + {3^2} + {4^2} + \cdots {k^2} + {(k + 1)^2} = \frac{{[k(k + 1)(2k + 1)]}}{6} + {(k + 1)^2}\)

\( = \frac{{[k(k + 1)(2k + 1)] + 6{{(k + 1)}^2}}}{6} = \frac{{(k + 1)[k(2k + 1) + 6(k + 1)]}}{6}\)

\( = \frac{{(k + 1)\left[ {2{k^2} + k + 6k + 6} \right]}}{6} = \frac{{(k + 1)\left[ {2{k^2} + 7k + 6} \right]}}{6}\)

\( = \frac{{(k + 1)[(k + 2)(2k + 3)]}}{6} = \frac{{(k + 1)[(k + 1 + 1)(2(k + 1) + 1)]}}{6}\)

\(=\)RHS

Thus, \(P(k+1)\) is true whenever \(P(k)\) is true.

Hence, \(P(n)\) is true \(\forall n \in N\)

Q5. Prove that \({2^n} \ge n + 1\) for all \(n \in N\)
Sol: Let \(P(n):{2^n} \ge n + 1\)

Let \(n = 1,P(1):{2^1} \ge 1 + 1 = 2,\) which is true

Assume \(P(k)\) is true for any natural number \(k\)

i.e., \({2^k} \ge k + 1……..\left( i \right)\)

We shall prove that \(P(k+1)\) is true whenever \(P(k)\) is true.

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

\({2.2^k} \ge 2(k + 1)\)

\( \Rightarrow {2^{k + 1}} \ge 2k + 2 > (k + 1) + 1\) is true.

\(∴ P(k+1)\) is true when \(P(k)\) is true.Hence, by the principle of mathematical induction. \(P(n)\) is true for all \(n.\)

Summary

Mathematical induction is a method of mathematical proof used to establish that a statement is true for all natural numbers \(n.\) The validity of mathematical induction is logically equivalent to the well-ordering principle. It has applications in real-life like the domino effect and family trees. There are two types of reasoning such as the process of deduction and the process of induction. If \(P(n)\) is a statement involving a natural number \(n,\) such that \(P(1)\) is true, i.e. the statement is true for \(n=1,\) and if \(P(k+1)\) is true whenever \(P(k)\) is true, i.e. the truth of \(P(k)\) implies the truth of \(P(k+1)\) then, \(P(n)\) is true for all natural number \(n.\)

Frequently Asked Questions (FAQs)

Q.1. What is meant by mathematical induction?
Ans: It is a method of mathematical proof that is used to establish that any given statement is true for all natural numbers \(n.\)
Here are the steps of mathematical induction:
Step 1: Prove that \(P(1)\) is true: i.e., \(P(n)\) is true for \(n=1\)
Step 2: Assume \(P(k)\) to be true; i.e., \(P(n)\) is true for \(n=k\)
Step 3: Prove that \(P(k+1)\) is also true ;i,e, \(P(n)\) is also true for \(n=k+1.\)
Hence, \(p(n)\) is true for all natural number \(n.\)

Q.2. What are the principles of mathematical induction?
Ans: If \(P(n)\) is a statement involving natural number \(n,\) such that
(i) If \(P(1)\) is true, i.e. the statement is true for \(n=1\)
(ii) If \(P(k+1)\) is true, whenever \(P(k)\) is true, i.e., the truth of \(P(k)\) implies the truth of \(P(k+1)\) then \(P(n)\) is true for all natural number \(n.\)

Q.3. What is the principle of mathematical induction in discrete mathematics?
Ans: It is a method of mathematical proof that is used to establish that any given statement is true for all natural numbers \(n.\) The method can also be used to extend the proof of statements for more general well-founded structures, such as trees; this generalisation, known as structural induction, is used in mathematical logic and computer science. This method is also used in discrete mathematics to prove the statements.

Q.4. How is mathematical induction useful when analysing problems?
Ans: Using mathematical induction reduces the given problem into a mathematical proposition or theorem to a simple statement that can be easily proved. Each statement serves as a step toward the solution of a larger proposition.

Q.5. What is the purpose of mathematical induction?
Ans: The purpose of mathematical induction is to provide the general proof of an equation or statements for all natural numbers, \(1,2,3,…,\) without doing individual calculations. This is done by making assumptions about what has been proved in the previous calculations.

Learn About Principle of Mathematical Induction Here

We hope this detailed article on the Method of Mathematical Induction will make you familiar with the topic. If you have any inquiries, feel to post them in the comment box. Stay tuned to embibe.com for more information.