Principle of Mathematical Induction

For any natural number, say N, the mathematical induction is a strategy for proving a statement, theorem, or formula which is assumed to be true. To prove that the establishing statement or result are formulated in terms of n, where n is a natural number, we follow steps, P(n) as mentioned below:

1. The statement is considered to be true for n = 1, P(1) is true.
2. If the statement is considered to be true for n = k, where k is some positive integer, P(k) is true.
3. Prove that the result is also true for P(k+1) for any positive integer k.

If all these conditions are fulfilled, then P(n) is true for all natural numbers.

Proof 

The first step in this principle where we take the trivial case is known as the factual statement. In the second step, we take a condition therefore it is called the conditional step. According to the steps mentioned above, then if the given assertion is true only for some positive integer k, then P(n) is true for n = k+1. The assumption taken at P(n) is valid for n = k is called the inductive hypothesis. Now we take a simple example to prove the hypothesis. We have to prove that the sum of first n odd numbers is the square of n.

1 + 3 + 5 + 7 + … + (2n-1) = n².

P(n): 1 + 3 + 5 + 7 + …+ (2n-1) =  n². 

We have to prove that P(n) is true for all n. 

Following the steps above,

We prove that P(1) is true. This is called the basic step.

1 =  1² which implies that P(1) is true.

Now, we suppose that P(k) is true for some positive integer k. Since P(k) is true, we have

1 + 3 + 5 + 7 + … + (2k-1) =  k²

Now we need to prove that P(k+1  is true. 

We already have

 1 + 3 + 5 + 7 + … + (2k-1) =  k²    —(1)

Consider

1 + 3 + 5 +  7 + … + (2k-1) + {2(k+1) – 1}    —(2)

     =   k² + (2k + 1) =   (k+1)²       [when using (1)]

For that reason, P (k +1) is true along with the inductive proof, which is now completed.

Therefore, P(n) is true for all of the natural numbers n.

History of Principle of Mathematical Induction

Proof by mathematical induction, unlike other concepts and procedures, is not the creation of a single person at a specific time. The Pythagoreans are considered to have understood the principle of mathematical induction. The mathematical induction concept is credited to the French mathematician Blaise Pascal. JohnWallis, an English mathematician, coined the term induction. Later, the idea was used to demonstrate the binomial theorem. DeMorgan made numerous contributions to the discipline of mathematics on a variety of topics. He was the first to define and identify “mathematical induction,” as well as construct De Morgan’s rule for determining a mathematical series’ convergence. G Peano set out to deduce the properties of natural numbers from a series of explicit assumptions, which became known as Peano’s axioms. The mathematical induction principle is a statement of one of Peano’s axioms.

Solved Examples

Example1

For all n ≥ 1, we have to prove that

1² + 2² + 3² + 4² + … n² = n(n+1)(2n+1)/6 

Solution 

Let the given statement become P(n), i.e., 

P(n) :1²  + 2² + 3² + 4² + … n² = n(n+1)(2n+1)/6 

For, say n = 1, 

Therefore, P(1): 1 =1(1+1)(2.1+1)/6 which is true. 

Now, assume that P(k) is true for some positive integer k, i.e., 

1²  + 2² + 3² + 4² + … k² = k(k+1)(2k+1)/6      —(1)

We shall now prove that P(k + 1) is also true. Now, we have 

(1²  + 2² + 3² + 4² + … + k² ) + (k+1)²

=  k(k+1)(2k+1)6 + (k+1)²        [when using(1)]

The equation becomes k(k+1)(2k+1)+6(k+1)²/6

=  (k+1)(2k²+7k+6)/6

=  (k+1)(k+1+1){2(k+1)+1}/6

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

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

Example2

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

Solution 

We write P(n) :  7n –  3n, that is divisible by 4. 

We need to note that P(1):  71 –  31 = 4, which seems to be divisible by 4. Consequently P(n) becomes true for n = 1.

Now, lets assume that P(k) is true for some natural number k,

i.e., P(k) :  7k –  3k is divisible by 4. 

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

Now, we need to prove that P(k + 1) is true at any moment P(k) is true. 

Now 7(k+1) –  3(k+1) = 7(k+1) –  7.3k + 7.3k –  3(k+1)

                                  = 7(7k –  3k) + (7-3) 3k  

                                  = 7(4d) + (7-3)3k

                                  = 7(4d) + 4. 3k

                                  = 4(7d + 3k)

From the last line, we get to see that 7(k+1) –  3(k+1) is divisible truly by 4. Therefore, P(k + 1) is true whenever P(k) is true. So, by using the principle of mathematical induction the statement is true for every positive integer n.

Conclusion

Here, we learned about the Principle of Mathematical Induction. It is defined as a method, which is used to establish results for the natural numbers. In simple terms, we can say that this method is used to prove if the statement or theorem is found to be true for all natural numbers. The proof involves two cases. We first prove the statement for n = 1, this step is called the base case. In the next step, called the induction step, we check if the statement holds for any given case n=k, then it must also hold for the next case n=k+1.