2. Principles of Mathematical induction and simple applications

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.