Chapter 4: Principle of Mathematical 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).

Principles of Mathematical induction and simple applications

Question 1:  Prove that m≥ 1 prove that, 1²+ 2² + 3² +4² +……+ m² = m(m + 1)(2m + 1)/6

Solution: Let the given statement be

 P(n) : 1²+ 2² + 3² +4² +……+n² = n(n + 1) (2n + 1) / 6
Let  n= 1 , then P(1) : LHS=1² =1  and RHS=1(1 + 1) (2 × 1 + 1) /6
= 1 × 2 × 3 / 6 = 1

Now LHS=RHS

So, P(1)  is true.

Now, let n=k, and assume X(P) to be true

 i.e.,P(k): 1²+ 2² + 3² +4² +……+k² = k(k+1) (2k+1) / 6                      (1)
We shall now prove that P(k+1) is also true,

so now we have,

Let n=k+1 , then P(k+1) : LHS=

1²+ 2² + 3² +4² +……+k²  + (+1)²
= k(k+1)(2k+1) / 6 + (k+1)²
= k(k+1)(2k+1)+6(k+1)² / 6
= (k+1) {( 2k² + k) + 6(k+1)} /6
= (k+1) (2k² +7k+6)/6
= (k+1) (k+1+1) {2(k+1) +1 }/6
So, P(k + 1) is true, whenever P(k) is true for all natural numbers.

Thus, P(n) is true for all n ÎN

Question 2: Prove that the sum of cubes of n natural numbers is equal to ( n(n+1)²)² for all n natural numbers.

Solution:

Let P(n):

1³+2³+3³+⋯+n³ = (n(n+1)²)²

Step 1: Let n=1 then P(1): LHS=1³=1

RHS=(1(1+1)²)² = 1

So P(1)  is true.

Step 2: Let n=k, then Assume P(k) is true

 i.e.,

P(k): 1³+2³+3³+⋯+k³= (k(k+1)²)² .

Step 3: Let n=k+1, then  P(k+1) : LHS=

                  1³+2³+3³+⋯+k³+(k+1)³ = (k(k+1)²)²+(k+1)³

                 ⇒1³+2³+3³+⋯+k³+(k+1)³=k²(k+1)⁴+(k+1)³

                 = k²(k+1)²+4((k+1)³)⁴

                 =(k+1)²(k²+4(k+1))⁴

                 =(k+1)²(k²+4k+4)⁴

                 = (k+1)²((k+2)²)⁴

                 =(k+1)²(k+1+1)²)⁴

                 =(k+1)²((k+1)+1)²)⁴

                      =RHS

So, P(k + 1) is true, whenever P(k) is true for all natural numbers.

Thus, P(n) is true for all n ÎN

Question3: Show that 1 + 3 + 5 + … + (2n−1) = n²

Solution: 

Step 1: Result is true for n = 1

That is 1 = (1)²  (True)

Step 2: Assume that result is true for n = k

1 + 3 + 5 + … + (2k−1) = k² 

Step 3:  Check for n = k + 1

i.e. 1 + 3 + 5 + … + (2(k+1)−1) = (k+1)² 

We can write the above equation as,

1 + 3 + 5 + … + (2k−1) + (2(k+1)−1) = (k+1)²

Using step 2 result, we get

k² + (2(k+1)−1) = (k+1)²

k² + 2k + 2 −1 = (k+1)² 

k² + 2k + 1 = (k+1)²

(k+1)² = (k+1)² 

L.H.S. and R.H.S. are same.

So, P(k + 1) is true, whenever P(k) is true for all natural numbers.

Thus, P(n) is true for all n ÎN

Question4:  Show that 2²ⁿ-1 is divisible by 3 using the principles of mathematical induction.

To prove: 2²ⁿ-1 is divisible by 3

Assume that the given statement be P(k)

Thus, the statement can be written as P(k) = 2²ⁿ-1 is divisible by 3, for every natural number

Step 1: In step 1, assume n= 1, so that the given statement can be written as

P(1) = 2²⁽¹⁾-1 =  4-1 = 3. So 3 is divisible by 3. (i.e.3/3 = 1)

Step 2: Now, assume that P(n) is true for all the natural number, say k

Hence, the given statement can be written as 

P(k) =  2^2k-1 is divisible by 3.

It means that 2^2k-1 = 3a (where a belongs to natural number)

Now, we need to prove the statement is true for n= k+1

Hence, 

P(k+1) = 2^2(k+1)-1 

P(k+1)= 2^2k+2-1

P(k+1)= 2^2k. 2² – 1

P(k+1)= (2^2k. 4)-1

P(k+1) =3.^2k +(2^2k-1)

The above expression can be written as

P(k+1) =3.2^2k + 3a

Now, take 3 outside, we get

P(k+1) = 3(2^2k + a)= 3b, where “b” belongs to natural number

So, P(k + 1) is true, whenever P(k) is true for all natural numbers.

Thus, P(n) is true for all n ÎN

Question5. n (n + 1) (n + 5) is a multiple of 3

Solution:

We can write the given statement as

P (n): n (n + 1) (n + 5), which is a multiple of 3

If n = 1 we get

1 (1 + 1) (1 + 5) = 12, which is a multiple of 3

Which is true.

Consider P (k) be true for some positive integer k

k (k + 1) (k + 5) is a multiple of 3

k (k + 1) (k + 5) = 3m, where m ∈ N …… (1)

Now let us prove that P (k + 1) is true.

Here

(k + 1) {(k + 1) + 1} {(k + 1) + 5}

We can write it as

= (k + 1) (k + 2) {(k + 5) + 1}

By multiplying the terms

= (k + 1) (k + 2) (k + 5) + (k + 1) (k + 2)

So we get

= {k (k + 1) (k + 5) + 2 (k + 1) (k + 5)} + (k + 1) (k + 2)

Substituting equation (1)

= 3m + (k + 1) {2 (k + 5) + (k + 2)}

By multiplication

= 3m + (k + 1) {2k + 10 + k + 2}

On further calculation

= 3m + (k + 1) (3k + 12)

Taking 3 as common

= 3m + 3 (k + 1) (k + 4)

We get

= 3 {m + (k + 1) (k + 4)}

= 3 × q where q = {m + (k + 1) (k + 4)} is some natural number

(k + 1) {(k + 1) + 1} {(k + 1) + 5} is a multiple of 3

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

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

Question 6. (2n +7) < (n + 3)²

Solution:

We can write the given statement as

P(n): (2n +7) < (n + 3)2

If n = 1 we get

2.1 + 7 = 9 < (1 + 3)² = 16

Which is true.

Consider P (k) be true for some positive integer k

(2k + 7) < (k + 3)² … (1)

Now let us prove that P (k + 1) is true.

Here

{2 (k + 1) + 7} = (2k + 7) + 2

We can write it as

= {2 (k + 1) + 7}

From equation (1) we get

(2k + 7) + 2 < (k + 3)² + 2

By expanding the terms

2 (k + 1) + 7 < k² + 6k + 9 + 2

On further calculation

2 (k + 1) + 7 < k² + 6k + 11

Here k² + 6k + 11 < k² + 8k + 16

We can write it as

2 (k + 1) + 7 < (k + 4)²

2 (k + 1) + 7 < {(k + 1) + 3}²

P (k + 1) is true for n=k+1  whenever P (k) is true.

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