1. Motivation and Process of proof by induction

Chapter 4

Principles of Mathematical induction

The Principle of Mathematical Induction

What is principle of mathematical induction ?

Mathematical Induction is a technique of proving a statement, theorem or formula which is thought to be true, for each and every natural number n. By generalizing this in form of a principle which we would use to prove any mathematical statement is 'Principle of Mathematical Induction'.

 

Steps:

1. Let the given statement be P(n)
2. The statement is true for n = 1 i.e., P(1) is true, and.
3. If the statement is true for n=k, where k is a positive integer, then the statement is also true for all cases of. n= k+1 i.e., P(k) leads to the truth of P(k+1).
4. Hence P(n) is true for all n Î N

Motivation and Process of proof by induction:

Mathematical Induction gets motivated by the real life examples like if we have a ladder to reach to the roof then how will you prove that you will reach at the top using these ladders.

• First thing we need to assure that can we reach to the first step of that ladder, as if we reach to the first step then only you can go to the second, third and so on. And if you will not reach to the first one then you cannot reach to the top.
• Second thing is if we count the steps of the ladder then if we assume that we can reach to the 4^th step then we can reach to the 5^th one also.

Let’s understand it in terms of numbers:

Let’s give the numbers to the ladders as number 1, 2, and so on. Let p (n) is the proposition to reach to the nth number of step. Now we have to prove that if we move to the any step then we can reach to the nth step.

This statement in mathematical term is the same as “for any k ≥ 0, if P (k) is true then P (k + 1) is also true.”

For this first we have to reach to the first step so in mathematical term, If P (1) is true, then only we can say that “if P (k) is true then P (k + 1) is also true” for k = 1 and then we get that P(2) is also true, which then indicates that P(3) is true, and so on, which shows that P(n) is true for all n ≥ 1. But if P (1) is not true, then P (n) also may not be true for any n ≥ 2.

Principle of Mathematical Induction

The above concept derives the principle of mathematical induction which is used to directly prove the statements given in terms of n natural numbers.

• Base Case: The given statement is correct for first n natural number that is, for n = 1, p (1) is true.
• Inductive Step: If the given statement is correct for any natural number like n = k then it will be correct for n = k + 1 also that is, if p (k) is true then p (k+1) is also true.

This principle says that if both the above steps are proven then p (n) is true for all natural numbers.

Example

Let’s take the example of the formula for the sum of the first n squares, for n ≥ 0. We will find a pattern in the sum of squares of n natural numbers:

0² = 0

0² + 1²  = 1

0² + 1² + 2² = 5

0² + 1² + 2² + 3² = 14

If we will follow this pattern we can see that the sum of the first n squares could be n (n + 1) (2n + 1)/6. Now we have to prove that this formula works for every number n ≥ 0, that is, we have to prove an infinite number of equalities. 

When can we use Mathematical Induction?

Mathematical induction can be used for so many statements where we want to show, that statement is true. Every statement cannot be proved by this new technique.

• First, in induction we need to find our statement P (n) for all integers n ≥ 0, so induction works only for the statements with the whole numbers. So, the statements like “For all x ∈ R, x² ≥ 0” will not be able to prove with  induction as the set of real numbers is not easy to calculate.
• Secondly, for our induction proof we have to follow the inductive step  that is, statements where the P (k+ 1) case is true assuming that the P (k) case is true are particularly well-suited for induction. For Example, statements involving sums  are suitable as it is easy to write the left-hand side of our statement P (k + 1) in terms of the left-hand side of the statement P (k).