Mathematical Induction

Mathematical induction is a concept that helps to prove mathematical results and theorems for all natural numbers. The principle of mathematical induction is a specific technique that is used to prove certain statements in algebra which are formulated in terms of n, where n is a natural number. Any mathematical statement, expression is proved based on the premise that it is true for n = 1, n = k, and then it is proved for n = k + 1.

Let us understand the concept of the principle of mathematical induction, its statement, and its application for proving various mathematical theorems and statements for natural numbers.

Mathematical Induction is a technique used to prove that a mathematical statements P(n) holds for all natural numbers n = 1, 2, 3, 4, ... It is often referred as the principle of mathematical induction. To prove a result P(n) using the principle of mathematical induction, we prove that P(1) holds. If P(1) is true, then we assume that P(k) holds for some natural number k, and using this hypothesis, we prove that P(k+ 1) is true. If P(k+1) holds true, then the statement P(n) becomes true for all natural numbers.

Now, let us state the principle of mathematical induction and understand how it is used to prove statements step-wise:

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.
2. If the statement is true n = k, where k is some natural number, then the statement is also true for n = k+1, i.e., the truth of P(k) implies the truth of P(k+1)

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

Now before we move on to solve a few examples using the principle of mathematical induction, let us go through some points that are important to understand:

• The first step is a statement of fact. Some mathematical statements hold true for n ≥ 5. In this case, to prove the result using the Principle of Mathematical Induction, step 1 will start from n = 5.
• Step 2 is a conditional property. It does not assert that the statement P(n) is true for n = k. It says that if the statement is true for n = k, then it is also true for n = k+1. In other words, we can say that we assume P(k) is true for some natural number k and then prove that P(k+1) is true.

Now, each step that is used to prove the theorem or statement using mathematical induction has a defined name. Each step is named as follows:

• Base step: To prove P(1) is true.
• Assumption step: Assume that P(k) is true for some k in N.
• Induction step: Prove that P(k+1) is true.

After proving these 3 steps, we can say that "By the principle of mathematical induction, P(n) is true for all n in N". The assumption that we make in the second step that P(n) holds for some natural number n = k is called induction hypothesis.

Now that we have understood the concept of mathematical induction, let us solve an example to understand its application better.

Example 1: Prove that the formula for the sum of n natural numbers holds true for all natural numbers, that is, 1 + 2 + 3 + 4 + 5 + .... + n = n(n+1)/2 using the principle of mathematical induction.

Solution: Suppose P(n): 1 + 2 + 3 + 4 + 5 + .... + n = n(n+1)/2

Here we use the concept of mathematical induction and prove this across the following three steps.

Base Step: To prove P(1) is true.

For n = 1, LHS = 1

RHS = 1(1+1)/2 = 2/2 = 1

Hence LHS = RHS ⇒ P(1) is true.

Assumption Step: Assume that P(n) holds for n = k, i.e., P(k) is true

⇒ 1 + 2 + 3 + 4 + 5 + .... + k = k(k+1)/2 --- (1)

Induction Step: Now we will prove that P(k+1) is true.

To prove: 1 + 2 + 3 + 4 + ... + (k+1) = (k+1)(k+2)/2

Consider LHS = 1 + 2 + 3 + 4 + ... + (k+1)

= 1 + 2 + 3 + 4 + ... k + (k+1)

= (1 + 2 + 3 + 4 + ... + k) + k+1

= k(k+1)/2 + k+1 [Using (1)]

= [k(k+1) + 2(k+1)]/2

= (k+1)(k+2)/2

= RHS

⇒ P(n) is true for n = k+1

Hence, by the principle of mathematical induction, P(n) is true for all natural numbers n.

Important Notes on Principle of Mathematical Induction

• Each mathematical statement is assumed as P(n) for a natural number n.
• First, we prove for n = 1, then assume for n = k and finally prove for n = k+1.
• The result of the "assumption step" is used after writing the k^th term (before the (k+1)^th term).
• If getting the RHS from the LHS seems difficult, simplify the LHS and the RHS separately and prove that they are equal.

Topics Related to Mathematical Induction

• Geometrical Proofs
• Triangle Inequality Theorem
• Sum of Natural Numbers

What Is Mathematical Induction In Maths?

Mathematical induction is the process of proving any mathematical theorem, statement, or expression, with the help of a sequence of steps. It is based on a premise that if a mathematical statement is true for n = 1, n = k, n = k + 1 then it is true for all natural numbrs.

What is the Principle of Mathematical Induction?

The Principle of Mathematical Induction is a technique used to prove that a mathematical statements P(n) holds for all natural numbers n = 1, 2, 3, 4, ... It helps to solve or find proof for any mathematical expression over a sequence of steps. It is proved for n = 1, n = k, and n = k + 1, and then it is said to be true for all n natural numbers.

What is the Use of Mathematical Induction?

The Principle of Mathematical Induction is important because we can use it to prove a mathematical equation statement, (or) theorem based on the assumption that it is true for n = 1, n = k, and then finally prove that it is true for n = k + 1.

What is the Principle of Mathematical Induction in Matrices?

The Principle of Mathematical Induction in matrices is a specific technique of proving statements or theorems based on matrices using mathematical induction.

How to Apply The Principle of Mathematical Induction?

To prove a result P(n) using the principle of mathematical induction, we prove that P(1) holds. If P(1) is true, then we assume that P(k) holds for some natural number k, and using this hypothesis, we prove that P(k+ 1) is true. If P(k+1) holds true, then the statement P(n) becomes true for all natural numbers.

What Are The Steps To Solve A Problem Using Mathematical Induction?

There are mainly two steps to prove a statement using the Principle of Mathematical Induction. The first step is to prove that P(1) is true and the second step is to prove P(k+1) is true using the truth of P(k). Then we can say that P(n) is true for all natural numbers n.

What are the Names of Each Of The Steps Used In Mathematical Induction?

Each step that is used to prove the theorem or statement using the principle of mathematical induction has a defined name. Each step is named as follows:

• Base step: To prove P(1) is true.
• Assumption step: Assume that P(k) is true for some k in N.
• Induction step: Prove that P(k+1) is true.