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