# mathematical induction in toc | mathematical induction in discrete mathematics in 5 minutes

Hey guys, welcome to our first ever theory

of computation(toc) tutorial. today we will be learning about, mathematical induction.

So before starting, i would like to request you guys to subscribe to my channel, second

thing, make sure you watch this video completely, its a short video but i am going to explain

it with the help of an example. SO to understand it properly, make sure you watch this video

completely. And third thing if you like it, share it with your friends, and hit that like

button. So lets get started, SO what is mathematical

Induction? Based on general observations, specific truths

can ve identified by reasoning. proof of mathematical induction involves four

steps. First step is called “Basis”: this is the

stating point for an induction. Here, its proved that the result is true for

same n=0 or n=1. Second step is called Induction Hypothesis.

So over here we assume that the result is true for n=k. SO first we prove that it is

true for n=0 or n=1 and then we assume that it is true for n=k.

Next thing is we prove that the result is true for n=k+1 and final step is called Proof

of induction step, where we actually prove that for n=k+1 it’s true.

So the four steps are, first step is Basis, second step is Induction hypothesis, third

step is Induction Step and fourth step is proof of Induction step.

Now we will look at an example so you will understand it better.

So for our example we are taking this simple one.

Prove the following series by principle of induction.

So what is is the series given to us?

1+2+3+….+n=n(n+1)/2 So we have to prove that this series is true.

So first step is called, Basis. Where we take n=1, Now lets say we substitute

the value of 1 over here so 1 means only one variable so L.H.S=1 and R.H.S=1(1+1)/2=2/2=1

SO L.H.S=R.H.S proved. SO result is true for n=1.

First step is done. Second step is Induction hypothesis. Now we

assume the result is true for n=k. thats why we just substitute instead of n

we substitute k. So we have 1+2+3+…+k=k(k+1)/2.

third step is Induction step: Over here what we do is we prove that the result is true

for n=k+1. So again what we have to do, we have to go

fo 1+2+3+…+k+k+1=(k+1)(k+1+1)/2 So you are replacing over here instead of

k, (k+1). Now FInal step is we have to prove that what

statement we have made is true of induction step.

Now L.H.S=1+2+3+…..+k+K+1, we already know what is the value of some part of the

L.H.S, why coz in the second step we have already got the value of part of L.H.S. which

is k(k+1)/2, so till here we know the value, which is k(k+1)/2.

SO we take that, plus k+1 So now this equation is k(k+1)/2+ k+1.

Now we just need to simplify this and just multiply this 2 over here and get this simple

equation. We get {k(k+1)+2(k+1)}/2. we get a quadratic equation {k square + 2k +2}/2

. this can be simplified as (k+1)(k+2)/2 k+2 can also be written as k+1+1. So hence we

get our R.H.S, which was (k+1)(k+1+1)/2. So we have proved that L.H.S=R.H.S so thats

how we do it. Alright, so the claim is true for n=k+1.

Since n can be any number this statement is true for all the values of n.

So this is how we prove using the mathematical induction.

SO if you have any doubt, feel free to ask them in the comments section below, ok, if

you like this video, make sure you subscribe and also hit that like button, share this

video with your friends, Thank you

Please Subscribe to my Channel. Thank you!!!

super bro ….. tell about recurence relation bro…

Mujh sab samjh aaya bus adding jo kare ap proof of I step par k+1 wo Hi samjh ni aaya plz reply me

Awesome sir nice steps

Explain recursion relation

Supp

thank you so much it is very easy nice video……………

Superb sir 👍👍👍

only reading

bore video ever

Aache se explane karona

can you please tell more examples for mathematical induction

Bro it helped me a lot bro Thankyou

. And I need a explaination of functions chapter all theroms. i.e bijection,injection

Please solve some more problems

nice

AmZing

Man u have done a superb work….

Helped me a lot

Thx sir

THANX a lot…much helpful….😊👍

I have my exams after 2 hrs and this video helped a lot!

Yar hindi me v bol sakte the

4th step me wo k2+3k+2. He usme wo 2 kaise aya

Thank you soo much it helped me a lot!!

Sir you liked all comments.pls like mine too.love you

Excellent explaination,made my work really easier,a big thanks..!!

I cannot understand ksquare line

Your language is easy to understand

Nice one

Awesome work keep it up

nice

Super

So amazing💕😍 best explanation

you are make very easy thanks

It was short but good easy language to understand sir can you plz tell me from where we can solve extra questions on net

Sir u r ossmm for explaining