Mathematical Induction

Introduction 

Mathematical induction is a special technique or a mathematical concept that proves specific statements in algebra. These algebraic statements are formulated in terms of n (n are the natural numbers). This technique proves that a mathematical statement P(n) will hold for the natural numbers, i.e. n = 1, 2, 3, 4, 5, 6, 7, 8, 9…

For proving, P(n) with mathematical induction, we shall first prove that P(1) holds. If we find that n(1) is true, then we can follow the assumptions that P(k) will hold for a certain natural number k. With this hypothesis, we can prove that P(k+1) shall be true. Now, as P(k+1) becomes true, then P(n) eventually becomes true for entire natural numbers. Read the article for the Mathematical induction study material.

Principle of Mathematical Induction

An integer (say x) is hereditary if it belongs to the class, and x+1 (the successor of x) also belongs to it.

The principle of mathematical induction states that if an integer (say O) belongs to a specific class, i.e. M, and M is hereditary. Then, every positive integer shall belong to class M. 

In its intensional form, the mathematical induction states that a property of an integer (say x) shall be hereditary if its successor also has the property. Therefore, if any integer ‘a’ has a specific hereditary property, then every positive integer might possess that property.

Understanding the Working of the Principle of Mathematical Induction

Let’s understand the working principle of mathematical induction. 

Assume any statement as P(n). This P(n) has only natural numbers, i.e. n, in a way that this statement becomes true for n = 1. We can say that P(1) is true. So as already discussed, when P(1) becomes true, then assume n = k (k is any natural number) is also true. 

Now, the statement needs to be proved true for n = k+1. Thus, P(k) implies P(K+1). Therefore, we can simply imply that P(n) holds true for all natural numbers. 

Proof by Mathematical Induction

Let’s assume an example of a case, i.e. the sum of the first odd and positive integers shall be n2 [i.e. 1+3+5+7+…+ (2n-1) =n2], i.e. the equation 1.

Let F as the class for which this equation holds true. Therefore, we can determine that n=1 belongs to class F. Now, 1 = 12. Any integer x belongs to F implies that,

[1 + 3 + 5 +⋯+ (2x − 1) = x2], i.e. equation 2

As we know that another odd integer after (2x − 1) is (2x + 1). We shall add this to both of the above equations. 

[1 + 3 + 5 +⋯+ (2x + 1) = x2 + 2x + 1 = (x + 1)2], i.e. the equation 3. 

So equation 2 regarded as hypothesis states that equation 1 shall hold true if n is x. On the other hand, equation 3 states about equation 1 that it holds true when n is x+1. As we know, equation 3 is already proved as a result of equation 2. Therefore, it shall be proved that if x belongs to F then definitely its (x) successor shall also belong to F.

So, according to the principle of mathematical induction, all the positive integers will also belong to the F.

Steps to Solve Mathematical Induction

A question on mathematical induction requires three basic steps to solve. These steps are as follows:

• First Step: The step involves proving P(1) as true. This step is also referred to as the base step. 
• Second Step: In the second step, you have to assume P(k) stands true for k in N. We assume this step, therefore it is the assumption step.
• Third Step: The third step involves the proving of P(K+1) as true. 

If these three steps are proved, then according to the principle of mathematical induction, we can state that P(n) is true for the natural number (n = k). This is the induction hypothesis.

Solved Question on Mathematical Induction

Question: To prove that 2n > n is for all positive integers n.

Solution: We shall prove this using the mathematical induction’s principle:

Assuming P(n): 2n > n

 Step 1: For proving P(1) holds true.

For n = 1, we shall have,

P(1) = 2 > 1

Therefore, P(1) is true.

Step 2: Assuming that P(n) will hold for n = k, 

i.e. P(k) is true

thus, 2k > k — (1)

Step 3: Proving that P(k+1) is true.

2k+2 > k + 1

Consider 2k+1 

= 2+2k> 2k [By using (1)]

= k + k> k + 1 [Because all natural numbers excluding 1 are greater than 1.]

Therefore, P(n) is true for n = k+1

Thus, by the principle of mathematical induction,

 P(n) will be true for all natural numbers (n).

Answer: Therefore, 2n > n is also true for all positive integers n.

Conclusion

Mathematical induction is a special technique or a mathematical concept that proves specific statements in algebra. These algebraic statements are formulated in terms of n (n are the natural numbers). This technique proves that a mathematical statement P(n) will hold for the natural numbers, i.e. n = 1, 2, 3, 4, 5, 6, … There are 3 steps in solving the question based on the principle of mathematical induction. If these three steps are proved, then according to the principle of mathematical induction, we can state that P(n) is true for the natural number (n = k). Thus, study notes on mathematical induction are necessary for solving algebraic questions.