# Mathematical Induction

Mathematical Induction is the important topic of the Theory Of Computation. Theory Of Computation is the Important subject of the Computer.

## Prove 7+ 13+19+…..+(6n+1)= n(3n+4)

**Step-1: Basic **

** **We must show that p(0) is true.

P(0)= 0(3(0)+4)=0

And, this is obviously true.

**Step-2: Induction Hypothesis **

** **k >= 0 and

p(k) = 7+13+19+…..+(6k+1)=k(3k+4)

**Step-3: Proof of Induction **

P(k+1) = 7+13+19+…..+(6k+1)+(6(k+1)+1)

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

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

= 3k^{2}+4k+6k+7

= 3k^{2}+10k+7

= 3k^{2}+3k+7k+7

= 3k(k+1)+7(k+1)

= (k+1)(3k+7)

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

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

Hence by principle of mathematical induction is true.

### Prove limit i=1 to n ∑ i * i !=(n+1)

**Step-1: Basic **

** **We must show that p(0) is true. ** **

P(0)= (0+1)! =(1)! = 1 And, this is obviously true.

**Step-2: Induction Hypothesis **

k >= 0 and p(k) = 1+(1+4+18+…..+(k*k!)) = (k+1)!

**Step-3: Proof of Induction **

P(k+1) = 1+(1+4+18+…..+(k*k!) +(k+1)*(k+1)!)

= (k+1)! + (k+1)(k+1)!)

= (k+1)! (1+(k+1))

= (k+1)! ((k+1)+1) = ((k+1) + 1)!

Moreover, Hence by a principle of mathematical induction is true.

#### prove limit i=1 to n∑(2i-1)=1+3+5+…….+(2n-1)=n^2

**Step-1: Basic **

** Moreover, **We must show that P(1) is true.

** **P(1) = (1)^{2 }= 1

And, this is obviously true.

**Step-2: Induction Hypothesis **

** **k >= 0 and

** **p(k) = 1+3+5+…..+(2k-1)=k^{2}

**Step-3: Proof of Induction **

P(k+1) = 1+3+5+….+(2k-1)+(2(k+1)-1)

= k^{2 }+ (2(k+1)-1)

.= k^{2 }+ (2k+2-1)

= k^{2 }+ 2k+1

=(k+1)^{2 }

Hence by principle of mathematical induction is true.

#### Prove n(n^{2}+5) is divisible by 6 for n>=0, Using Principle of Mathematical Induction.

**Step-1: Basic step **

Moreover, We must show that p(0) is true.

P(0)=0(0^{2}+5)=0*6/6=0

And, this is obviously true.

**Step-2: Induction Hypothesis **

For k>=0 and

P(k)=k(k^{2}+5) is divisible by 6.

Statement to be shown in Induction step is, P(k+1)=(k+1)[(k+1)^{2}+5] is divisible by 6.

**Step-3: Proof of Induction **

(k+1)[(k+1)^{2}+5]

=k[(k+1)^{2}+5]+1[(k+1)^{2}+5]

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

=k^{3}+2k^{2}+k+5k+(k^{2}+2k+6)

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

= k(k^{2}+5)+2k^{2}+k+k^{2}+2k+6

Moreover, = k(k^{2}+5)+3k^{2}+3k+6

= k(k^{2}+5)+3k(k+1)+6

Here, k(k^{2}+5) is divisible by 6 ,given in induction hypothesis.

In Second term k and k+1 are consecutive. So, one number is even and one is odd. So, the even number is always multiple of 2 and here 3 is also present.So, the second term having (2*3) is also divisible by 6.

Last term 6 is obviously divisible by 6.Hence proved.

#### Strong Principle of Mathematical Induction

Suppose p(n) is a statement involving on integer n then to prove that p(n) is true for every n>= n_{0}. It is sufficient to show these two conditions

P(n_{0}) is true

For any k >=n_{0} , if p(n) is true for every n satisfying n_{0}<=n<=k then p(k+1) is true.

**Related Terms**

Theory of Computation, PDA – CFG, Union, Intersection & Compliment operation, Context Free Grammar

## Leave a Reply