Method of Mathematical Induction

Method of Mathematical Induction

*******************************

In Mathematical Induction, first we prove it for n=1. Then assume it to work for n=k.

Prove that it works for n=k+1.

For example 

let us take the formula : Sum of n natural numbers = n(n+1)/2

1+2+3+4+5+6+..........+n = n(n+1)/2

By mathematical induction, 

first take n=1.

1+2+3+...1 = 1(1+1)/2

Therefore,

1= 1(2)/2

1=1

Hence proved for n=1.

Now assume that the above said formula works for n=k.

i.e.

1+2+3+4+.....+k = k(k+1)/2

Assumed.

Now I have to prove for n=k+1

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

Now what we do is break

1+2+3+4+5+.......(k+1)   into   1+2+3+4+5+6+......+k+(k+1)

That is the term before (k+1)

is k.

So 

1+2+3+4+5+6+7+8+.........+k+(k+1)

can be split as 

k(k+1)/2 +(k+1)

(k+1)((k/2)+1)

i.e .(k+1)(k+2)/2

Hence proved for (k+1).

i.e. to prove for n=k+!

we take the series for n=k+1

we split it to term before k+1 and the (k+1)th term.

the terms before k+1th term i.e. summation of terms upto k is taken from the assumption 

we held for summation upto k terms. 

Thus proved.