Last Updated on: 16th February 2024, 02:07 pm

Mathematical Induction

Mathematical Induction – Meaning

In general, the word Induction means the generalisation from particular cases or facts. In Mathematics, there are certain results or statements that are formulated in terms of n, where n is a positive integer. We may prove such general cases from Initial Base step to next one through the Mathematical Induction.

Mathematical Reasoning

Mathematical Reasoning is the process of finding the proof for a certain mathematical statement by using logic and deductions. Inductive and deductive reasoning are two fundamental forms of reasoning for mathematicians. The formal theorems and proofs that we rely on today all began with these two types of reasoning.

• Mathematical Deduction : Deduction is drawing a conclusion from something known or assumed, normally used in almost every step in a mathematical argument.
  For example, to solve 2x = 6 for x we divide both sides by 2 to get or x = 3. Here we assume that 2x = 6 and that you can divide both sides of an equation by any non-zero number and the equation is still valid. From these two facts we deduce that x = 3.
• Mathematical Induction : Mathematical induction is a particular type of mathematical argument. It is most often used to prove general statements about Positive Integers.
  For example, we may use mathematical induction to prove that for every positive integer n, (1 + 2 + 3 + … + n) = 
  To find the formula for the sum of positive integers 1, 2, 3,…,n, that is, a formula which will give the value of 1 + 2 + 3 when n = 3, the value 1 + 2 + 3 + 4, when n = 4 and so on. Let us suppose somehow we are led to believe that the formula (1 + 2 + 3+…+ n) =  is correct.

To prove the formula, we may verify the statement for as many positive integral values of n as we like, but this process will not prove the formula for all values of n. We need is some kind of chain effect which will have the effect that once the formula is proved for a particular positive integer, the formula will automatically follow for the next positive integer, and the next indefinitely. Such chain effect is produced by Mathematical Induction.

Mathematical Induction Principles

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

(i) The statement is true for n = 1, i.e., P (1) is true, and

(ii) 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.

Here, Property (i) is simply a statement of fact. When a statement is true for all n ≥4, we start from n = 4 and verify the result for n = 4, i.e., P(4).

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

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

This is referred to as the inductive step. The assumption that the given statement is true for n = k in this inductive step is called the inductive hypothesis.

Mathematical Induction – Example 1

Let us explain with an example. We observe that:

1²=1

2²= 1 + 3

3² = 1 + 3 + 5

4² = 1 + 3 + 5 + 7, etc.

So, we see that sum of first two odd natural numbers is the square of second natural number, sum of first three odd natural numbers is the square of third natural number and so on. Thus, we may mathematically express this observation as :

1 + 3 + 5 + 7 + … + (2n – 1) = n² , i.e, the sum of the first n odd natural numbers is the square of n.

So, for the property P(n): 1 + 3 + 5 + 7 + … + (2n – 1) = n², prove that P(n) is true for all n.

• Basic Step : The first step (called basic step) in mathematical induction is to prove that P (1) is true.

We see, 1 = 1², so, P(1) is true.

• Inductive Step : The next step ( is called inductive step), we assume that P (k) is true for some positive integer k and we need to prove that P (k + 1) is true.

Since P (k) is true, we have 1 + 3 + 5 + 7 + … + (2k – 1) = k² .

Adding {2(k +1) – 1}, or (2k+2-1) or (2k+1) to both sides, we have :

1 + 3 + 5 + 7 + … + (2k – 1) + {2(k +1) – 1} = k² + (2k + 1) = (k + 1)²

Therefore, P (k + 1) is true and the inductive proof is proved..

Hence P(n) is true for all natural numbers n.

Mathematical Induction – Example 2

Prove that 2ⁿ > n for all positive integers n.

Let P(n): 2ⁿ > n. When n =1, 2¹ >1. Hence P(1) is true.

Assume that P(k) is true for any positive integer k (k>1), i.e., 2^k > k

Multiplying both sides of by 2, we get , 2 x 2^k > 2k, Or, 2 ^{(k + 1)} > 2k. So, 2 ^{(k + 1)} > k + k > k + 1 (as k>1)

Therefore, P(k + 1) is true when P(k) is true. Hence, by principle of mathematical induction, P(n) is true for every positive integer n.

Mathematical Induction – Example 3

Prove that(ab)ⁿ= aⁿbⁿ, for every natural number.

P(n) : (ab)ⁿ= aⁿbⁿ. we find that (ab)¹ = a¹b¹. So, P(n) is true for n = 1

Let us assume that P(k) be true, i.e (ab)^k = a^kb^k.

 (ab)^{k + 1} = (ab)^k (ab) = (a^k b^k) (ab) = (a^k. a¹)  × (b^k. b¹) = a^k+1 × b^k+1

Therefore, P(k + 1) is also true whenever P(k) is true. Hence, by principle of mathematical induction, P(n) is true for all n ∈ N.

Mathematical Induction – Example 4

For every positive integer n, prove that 7ⁿ– 3ⁿis divisible by 4.

This statement can be written as: P(n) : 7ⁿ – 3ⁿ is divisible by 4.

P(1): 7¹– 3¹ = 4 which is divisible by 4. Thus P(n) is true for n = 1

Let us assume P(k) is true for some natural number k,

So, P(k) : 7^k– 3^kis divisible by 4.

We can write 7k – 3k = 4d, where d N.

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

Now 7^{(k + 1)} – 3^{(k + 1)} = 7^{(k + 1)} – 7.3^k + 7.3^k – 3^{(k + 1)} (Adding and subtracting 7.3^k, so value remains same)

= 7(7^k – 3^k) + (7 – 3)3^k = 7(4d) + (7 – 3)3^k

= 7(4d) + 4.3^k = 4(7d + 3^k). So, it is seen that 7(k + 1) – 3(k + 1) is divisible by 4.

Thus, P(k + 1) is true when P(k) is true. Therefore, by principle of mathematical induction it is proved that the statement P(n) : 7ⁿ – 3ⁿ is divisible by 4, is true for every positive integer n.