what is Mathematical Induction, solved problems on Mathematical Induction

 Mathematical induction is a mathematical technique to prove statements. mathematical induction involves two steps:

1. Basic step: to prove the given statement is true for the initial value. (f(0) is true)
2. induction step: to assume statement true for k ( F(k) is true) and then prove it is true for F(k+1) then p(n) is true for natural numbers.

Examples:

1. Prove that 5ⁿ - 1 is divisible by 4 for all n>=1

solution:

step-1: basic step : true for n=1

F(n)=5ⁿ - 1 

F(1)=5¹-1

F(1)= 4

F(n) is true for n=1

step 2: Induction step

first, we will assume the given statement is true for value k i.e.

2. Prove that n³ + 2n is divisible by 3 for all n>=1.

solution:

step-1: basic step : true for n=1

F(n)=n³ + 2n

F(1)=(1)³+2(1)

F(1)=1+2

F(1)=3 which is divisible by 3.

hence the given statement is true for n=1.

step 2: Induction step

first, we will assume the given statement is true for value k i.e.

F(k): k³-2k=3m is true

to prove : 

F(k+1): (k+1)³+2(k+1)=3m is true

proof:

RHS=(k+1)³+2(k+1)

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

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

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

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

RHS=(k³+2k)+3k²+3k+3

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

  here,             

F(K)=(k³+2k) and  3m=3(k²+k+1)

RHS=F(k) + 3m 

so it is true for F(k+1)

and hence it is proved n³ + 2n is divisible by 3 for all n>=1.

    3. prove this 1+2+3+-------+n = n(n+1)/2

solution:

step-1: basic step : true for n=1

F(n): 1+2+3+-------+n = n(n+1)/2

LHS=  1 for F(1)

RHS= n(n+1)/2=(1+1)/2=1=LHS 

so the given statement is proved for F(1)

step 2: Induction step

first, we will assume the given statement is true for value k i.e.

F(k): 1+2+3+-------+k = k(k+1)/2  is true     ..... eq 1

To prove:

F(k+1): 1+2+3+-------+(k+1)= k((k+1)+1)/2  is true........eq 2

from eq 1.

1+2+3+-------+k = k(k+1)/2

by adding (k+1) to both sides

1+2+3+-------+k+(k+1) = k(k+1)/2 +(k+1)

1+2+3+-------+k +(k+1)= k(k+1)+2(k+1)/2

1+2+3+-------+k +(k+1)= (k²+k+2k+1)/2

1+2+3+-------+k +(k+1)= (k²+3k+1)/2

k²+3k+1=k²+2k+K+1

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

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

1+2+3+-------+k +(k+1)=(k+2)(k+1)/2

hence proved F(k+1) is also true 

and hence the given statement is true.

    3. Prove this: 1+3+5+------+(2n-1)=n²

Solution:

step-1: basic step : true for n=1

F(n): 1+3+5+------+(2n-1)=n²

LHS=1

RHS=(1)²=1=LHS

hence F(1) is true.

step 2: Induction step

first, we will assume the given statement is true for value k i.e.

F(k):1+3+5+------+(2k-1)=k²  .....eq (1) is true.

To prove:

F(k+1):1+3+5+------+(2(k+1)-1)=(k+1)² .... Eq (2)

Proof:

LHS=1+3+5+------+(2(k+1)-1)

LHS=1+3+5+------+(2k+1)

LHS=1+3+5+------+(2k+1)

 last second odd term is (2k-1){(2k+1-2)  # difference between two consecutive odd term is 2}

LHS=1+3+5+------+(2k-1)+(2k+1)

{1+3+5+------+(2k-1)=F(k)=k²}

LHS=k²+2k+1

LHS=(k+1)²=RHS

hence proved the given statement is true for F(k+1)

and hence the given statement is true for n.

    4.prove that n³-n is divisible by 3for any positive integer n.

Solution:

step-1: basic step : true for n=1

F(n): n³-n = 3n

F(1):1-1=0 which is true for F(1)

step 2: Induction step

first, we will assume the given statement is true for value k i.e.

F(k):k³-k=3m  is true 

To prove:

F(k+1): (k+1)³-(k+1)=3m

Proof :

LHS=(k+1)³-(k+1)

LHS=(k³+1+3k²+3k)-k-1

LHS=k³+3k²+3k-k

(k³-k =3m means it is divisible by 3)

(3k²+3k is also diviblr by 3)

hence it is proved for F(k+1)

and the given statement is true for n.

    5. prove that (3ⁿ-1) is a multiple of 2.

solution:

step-1: basic step : true for n=1

F(n):3n-1 

F(1)=3-1=2 which is a multiple of 2.

step 2: Induction step

first, we will assume the given statement is true for value k i.e.

F(k): is true

3k−1

$\mathrm{<br>}$

3k−1
3k−1
3k−13k−1 is a multiple of 2 is to prove:

F(k+1) :

3k+1–1           is a multiple of 2

proof:

3k+1−1=3×3k−1=(2×3k)+(3k−1)

so it is proved for F(k+1)

and hence it is true for n also.