MATHEMATICAL INDUCTION - DISCRETE MATHEMATICS
Vložit
- čas přidán 25. 12. 2014
- We introduce mathematical induction with a couple basic set theory and number theory proofs.
#DiscreteMath #Mathematics #Proofs #Induction
Visit our website: bit.ly/1zBPlvm
Subscribe on CZcams: bit.ly/1vWiRxW
-Playlists-
Discrete Mathematics 1: • Discrete Math (Sets, L...
Discrete Mathematics 2: • Discrete Math (Countin...
-Recommended Textbooks-
Discrete and Combinatorial Mathematics (Grimaldi): amzn.to/2T0iC53
Discrete Mathematics (Johnsonbaugh): amzn.to/2Hh7H41
Discrete Mathematics and Its Applications (Rosen): amzn.to/3lUgrMI
Book of Proof (Hammack): amzn.to/35eEbVg
Like us on Facebook: on. 1vWwDRc
Hello, welcome to TheTrevTutor. I'm here to help you learn your college courses in an easy, efficient manner. If you like what you see, feel free to subscribe and follow me for updates. If you have any questions, leave them below. I try to answer as many questions as possible. If something isn't quite clear or needs more explanation, I can easily make additional videos to satisfy your need for knowledge and understanding.
![[Discrete Mathematics] Mathematical Induction Examples](http://i.ytimg.com/vi/KW5k7ZsQmwo/mqdefault.jpg)
![[Discrete Mathematics] Mathematical Induction Examples](/img/tr.png)
How many CS students are watching these vids?
69 cs students XD
Brazil
@@filspyrospapabundus lol
@@monavie9110 lol
@Bryant Shiloh No, no one cares. Totally fucking stupid to post this on a mathematical induction lecture video.
good luck to all CS students watchin this. LET'S GET THIS DEGREE AND CLAIM THE BAG!
2:50 format
4:05 first example
8:57 first example solution
9:05 second example
12:44 second example solution
I swear if you were my teacher for every math course I wouldn't have to force myself to go, and I'd actually want to show up to class. I don't understand why but it's hysterical how well you teach this xD
6:57 should read (k(k+1) + 2(k+1))/2 which will give you (k^2 + 3k + 2)/2, then you factor that into (k+1)(k+2)/2
where does the 2 come from in the first?
@yusram.6175 when dividing the (k+1) on the left side by 2 in order to get common factor. He was supposed to multiply the top as well so that k+1 stayed the same value
Thanks, was doubting myself at first lol
Here is the ladder example from a textbook:
"Suppose that we have an infinite ladder, as shown in Figure 1, and we want to know whether
we can reach every step on this ladder.We know two things:
1. We can reach the first rung of the ladder.
2. If we can reach a particular rung of the ladder, then we can reach the next rung.
Can we conclude that we can reach every rung? By (1), we know that we can reach the first
rung of the ladder. Moreover, because we can reach the first rung, by (2), we can also reach the
second rung; it is the next rung after the first rung. Applying (2) again, because we can reach
the second rung, we can also reach the third rung. Continuing in this way, we can show that we
can reach the fourth rung, the fifth rung, and so on. For example, after 100 uses of (2), we know
that we can reach the 101st rung. But can we conclude that we are able to reach every rung
of this infinite ladder? The answer is yes, something we can verify using an important proof
technique called mathematical induction. That is, we can show that P(n) is true for every
positive integer n, where P(n) is the statement that we can reach the nth rung of the ladder."
which book is this?
@@KixSoso Kenneth Rosen DMGT
I got stuck on something pretty stupid here: I saw ((k+1)[(k+1)+1]) simplify into ((k+1)[k+2]) and couldn't understand why, because for some reason I was reading the [(k+1)+1] part as [(k+1)1]. I know it's stupid, but because it's not factoring: [(k+1)+1] = (k+1+1) = (k+2).
Not sure if anyone got stuck on this same thing, but there you go.
Thanks, this really helped.
Everyone goes through this pain to get the success. But indeed the only success is the meeting with the Almighty God. We are never going to return to this world.
We've all been there man lol
@@ridovercascade4551 U r funny
I can do nothing about the truth brother, maybe next year, maybe next month, maybe tomorrow, maybe in 2 hours maybe now in 10 seconds? We die once, make sure you die as a man, and have a great life in both of the worlds.
Million thanks and virtual hugs! Your videos saved me from my dicrete mathematics couse in Spanish (my native language Finnish) which I'm taking in my exchange year in Peru;) I would have failed it for sure without your help. Thanks thanks thanks. Keep up the good work!
I took discrete math years ago and this video helped sooo much! You are the man!
Love your videos thank you so much.. I took a mandatory intro discrete course for CS... We covered video 1-28 in two weeks. Were on the third week and started graph theory and i'm so behind. Thanks so much for the informative videos, they're the only thing keeping me alive. (7 week courses)
You guys are so.lucky that you have this CZcams now. When I first encountered this stuff 30+ years ago I had nothing, nothing. And our textbook Elementary Number Theory by Burton was very little help. Still pretty "greek" though.
@@glennredwine289 true
5:25 Sorry, I got a little lost at where (K+2) came from.
At this stage, on the right side of the equation (K(K+1)), is it that both K's are replaced with K+1, making it so that its (K+1)((K+1)+1) = (K+1)(K+2)?
Thanks. Watching the previous videos in this series along with Hammack's Book of Proof sets the stage for intuitively understanding Proof by Induction. MIT's OCW Math for CS on the other hand jumped into it with very little background and so was far less clear.
Thank you so much for this, my teacher is a joke and this video just saved me about 3 hours of headaches.
I feel that's the way people really want to teach you to learn. My teacher always ignore most of the explanation and assume student knows it from the start, and start all of his proofs.
I totally understand NOTHING !! i hate this chapter...
i feels u bro
same
:(
but it is really easy when you understand clear concept
@@MDArif-xy5cc stfu
This guy needs to be inducted into the hall of fame for math instructors
I've never heard induction explained like this, thanks.
I'm watching though the course on discrete maths, and really appreciate you for producing it and making it available. Thank you. Makes me wonder what the hell was I doing when this was teached at elementary and highschool, since I have no memories from there but all of this makes so much sense now
+Mace Ojala Sometimes it just takes a different style of teaching to help. Glad you're enjoying it.
That's right. Plus >20 years of time and life experience in other areas makes a difference too, I bet.
@@TrevtutorEnjoying!
I might survive discrete math yet thanks to you!
did you survive ? asking for a friend xD
@@mouadrimwind8839 did you survive? Asking for my grandma
@@rishanaaishath8211 passed with C+ Lowest grade in my transcript so far but I did pass ouff
@@mouadrimwind8839 JUST SO MUCH GARBAGE!!
i did not survive, failing an exam as we speak
Thank you, video was really helpful and everything was explained really clearly!
In step 3 I found it easier to factor out a k+1 in the left side, which leaves you with (k+1) * (k/2) + 1 Then it is convenient to convert 1 = 2/2, when you simplify (k+1) * (k/2 + 2/2) you get (k+1) * (k + 2)/2 ..... and that is exactly the same as the right side of the equality. Hope I could help at least one poor soul taking this course XD good luck :)
thank you so much for this video. studying for finals I was struggling on proving summations via mathematical induction, and I had no idea how to find what it is that I was trying to prove, since our professor seemed to skim over the inductive hypothesis portion, and this video greatly helped. so thank you for this, keep it up.
Your videos are the best! Watching this b4 exams tomorrow
Thank you. I am studying for my cset, this helped out alot.
I think this finally made the principle click for me. Also thank you for addressing the circular reasoning argument. That's something I always struggled with.
You better explain the subject in first 2 minutes than my discrete math professor does in 2 x 1,5h lectures
Do you have any videos on strong induction and recursion?
I believe technically what he was showing IS the strong induction. The simple induction would be just assuming (n=k to be true), but he did (n
I'm taking a math class in highschool as a junior and this is one topic that is difficult for me😭 the way my teacher explained it wasn't the best thank you!
I think I wanna marry you no homo that ladder analogy was godly. Our prof only splatters examples to us and never really explained anything about the logic behind the induction solution (the proving of k+1) this has taught me more than our 90 minute session. Godspeed to you trev.
thank u very much!!! wish me luck on my exams 😊😊
This is a very good video. Thank you.
Thank you.Your videos are the best
Thanks a lot man. That really helped me out.
Thank you! Thank you SO MUCH!
I have so many of them
1) how do I prove log 6 base(4) is irrational
2) how do I prove using well ordering principle: n
Hello, thanks for the lesson.
From the first example, where you initially made a mistake. I did not catch your explanation on where the 2 you later added came from. Thanks
Thank you very much. I really love your videos. You are the best)))
This video is on my syllabus
simply amazing keep on the great work!!!
I loveee your handwriting!!! 💕💕💕
how did you get the (k+2) in the second step ???
I have a problem here prof n^4 < 4^n, for n> 4, would you help me with this one?
what program did you use?
Thank you for this video. But can you explain strong induction please. Thank you.
haaah
12:14 "Ass."
That's the most important part. Is for something to hold forever... *cries in math*
Bro i aint gonna lie, i didn’t study at all throughout this sem😭😭😭 rewatching all your videos two nights before my finals , really helping doooooooooo
how'd it go? likely failed...
Good work. Thanks
Hmm weird we never do it with n
this video really helped me. thank you so much
Same lol
Thanks soooo much!
best teacher!
Thank you!
It would be better if you took recurrence relations as an example for the "Induction Proof". Anyway gold content!
Man I love discrete math it’s so damn interesting
well explained sir
can someone please explain the factoring technique that was used? Every single video that does this proof (I've watched 4) doesn't explain where I can find more information on this, they just assume I've memorized every single little thing in algebra that I did 4 years ago.
Great video
Hey can you add Strong mathematical induction ??
amazing explenation
thanks for the help
High quality video
that was so useful!
well understood
how do you know what to choose for your base case for any given problem? what is the strategy for choosing the base case?
rainorchid1 You always start with 1, n=1.
Hi Trev, where did K+2 come from? This has been troubling me since my discrete class the other day. (k(k+1)(k+1))/2 = ((k+1)(k+2))/2; unless I am getting my math wrong I don't see how this is? I just really need to know where the number is coming from for me to understand.
+Christopher Naron k(k+1)(k+1)/2 is not equal to (k+1)(k+2), but k(k+1)/2 + (k+1) is. This is explained at 6:50 when I correct my error.
+Christopher Naron he basically modified the (k+1) a bit from the RHS by simply multiplying it by 2/2. Reason for this is to combine like terms and since 2/2 is equal to 1, it's equivalent to multiplying (k+1) by 1, which leaves it unchanged. It gets weirder with factorials, but it will make sense with practice.
+Christopher Naron Not sure if this is what you meant, but for subbing in k+1 to k(k+1)/2 it's (k+1)((k+1) + 1)/2 = (k+1)(k+2)/2
+Christopher Naron We are using a simple truth to prove a comlex problem. Since any number + 1 is the number ahead of it we can show all of these numbers with n +1. We assumed n = k( that if it worked for 1 it will work for an arbituary number k. And in order to prove this formula we want to show that it is true for k + 1. We need to apply k + 1 to the formula that was proven true with our base case k(k+1)/2 in order to see if this holds true for any real number. so replace k in the known forumula. k +1((k+1)+1) / 2 SImplify to (k+1)(k+2) / 2 Just think of it as using the simplest case that we know is true to work out the answer for the larger question that we dont know how to do by adding in the larger part of the problem k +1 ( or inducting it ) into or simple part of the problem we proved with our base case.
@@RedQueenAvenged but that's not what happened, right?
Why should I use this in practice? Maybe to prove my algorithm holds true to any random value?
Pls can you make another video explaining the last proof you just explained in this video???
Thank you kind sir
really cool! Discrete math is the coolest thing ever! specifically the proofs. It really helps us to understand the world with mathematical perspective.
So with the ladder analogy what happens if your chosen k is the last step on the ladder would it therefore not have a k+1?
This video assumes it's infinite, however, you can either
(a) prove n-1 -> n instead of n -> n+1 or
(b) show that n -> n+1 up to a boundary point and show that at some boundary k k+1.
@@Trevtutor That makes sense, thank you!
I think you made a mistake isn't k(k+1)/2 + (k+1) the same as (k(k+1)+2*(k+1))/2? Not just plopping the k+1 on the top of the fraction? Edit: You fixed your error like 10s after I paused whoops
+Taziod I don't understand where did the 2 in (k(k+1)+ 2 *(k+1))/2 come from ???
The 2 comes from the fact that you're adding a rational number and a number that isn't rational. To do this, they must have the same denominator. (k+1) is equivalent to (k+1)/1. So, to make its denominator 2, you simply multiply the numerator and denominator by 2. So, you end up with k(k+1)/2 + 2(k+1)/2. This is equal to (k(k+1) + 2(k+1))/2.
so what you're saying is he's wrong right Chunk?
@Edwin Kaburu yep
don't you think here k
thanks bro
How do you simply it at 6:18
Whats the bar ontop?
Gud day. pls, I wnt to no what topics I need to no before I can learn mathematical induction. Thanks
Algebra skills. Induction is a proof method, so if you want to do it on sets, you should know set theory etc.
I have a discrete math exam today so can someone please tell me how at 7:36 he went from k(k+1)/2 +(k+1) for the left hand side to k(k+1)+*2*(k+1)/2?? where did that 2(k+1) come from? am I missing something? Shouldn't it be just (k+1)?
I had this same question but I think I got it now. In order to add k(k+1)/2 to (k+1) we need to find a common denominator. Meaning 2(k+1)/2 is the same as (k+1). The 2/2 cancels out.
7:58 I like your stroke order heheh
why did you use N
i agree... i also wonder why?
k is a constant, while n is not.
because it doesn't matter. It's the same meaning.
because n is the infinite bracket of the question. K can either be within or be the last step of the ladder(n), but it can't surpass the infinite ladder n hypothetically.
because if he didn't do n
Great video. It's probably worth noting that this is a demonstration of strong induction, as opposed to regular induction; where during the induction hyp. you assume that your statement P(n) holds for some arbitrary k, then show it's also true for k+1.
u said you put in k+1 for k at 5:36, but wouldn't that end of being (K+1)(K+1)? Why is one of them K+2?
It would help if instead of making mistakes, continuing, realizing the mistake and then erasing a couple things, you just re-recorded the part. It really messes with understanding when you continue with incorrect work. For example, around the 5-8 minute mark, you changed the (k*(k+1))/2 multiple times, so the steps didn't make much sense
At 7:30 you change it to 2(K+1) why is that?
coz 2(k+1)/2 =(k+1) itself,the reason he did is to get same denominator in LHS as RHS
Hello, PLease help with the following problem
Prove (using direct proof) that, for all integers a and b, if a 𝑚𝑜𝑑 4 = 3 and b 𝑚𝑜𝑑 4 = 2,
Then ab 𝑚𝑜𝑑 4 = 2.
How do you write on your computer? With a mouse? I'm only curious because if you're using a mouse your handwriting is amazing.
+Taziod No, with a pen. This writing looks not great because there was no pressure enabled. Videos like in Discrete Math 2 have pressure enabled so it looks better.
I LOVE YOU!
I feel 'proof by induction' is a circular argument -- how can we 'assume' what we have set out to prove? What lends legitimacy to this assumption? What's the proof that proof by induction is a valid method of proof?
You do not assume what you are setting out to prove.
You show that it's true for the base.
Then you assume that for any given step k, k+1 is true.
Because k -> k+1, if it's true for 0, it's true for 1, then it's true for 2, then it's true for 3, etc. \
A proof of it is here en.wikipedia.org/wiki/Mathematical_induction#Equivalence_with_the_well-ordering_principle.
hi i know this is 9 years old but how did you get the k(k+1) + 2(k+1) at 7:30
Can someone explain to me why we do +2(k + 1) around the 7:30 mark. I'm not great with algebra
Trying to clutch. Wish me luck
howd it go
why do we assume n
It means that K is bigger than N, so you can regress back to the base case after K-N applications.
where did the (k+1)(k+2) come from?
what if the first step is false..i mean the basis???
5:22 I saw you add k+1 on the left side but there is still a k there. I mean that k should be replaced by k+1, then why there are even two k there?
The sum on the left is 1 + 2 + 3 + 4 + ... + n. Replace n with k+1, it becomes 1 + 2 + 3 + 4 + ... + (k + 1). Just like the number 3 came before the number 4, what number came before k+1? Well, it's k, right? (k + 1) - 1 = k. So we just reveal the number in the sum before k + 1 to be k, and so the sum is shown as 1 + 2 + 3 + 4 + ... + k + (k + 1). Get it?
This was easy in A Level Maths but now it's harder because of sets.
Isnt it strong induction?
ELON IS TEACHING US !
why did you use n< or = k , not n> or = k? Aren't we using natural numbers? means > or = 1
n =1, so we can't assume it.
Where did the k+2 come from in the first example though?
This comes from plugging (k+1) into the original formula n*(n+1)/2.
Replace "n" with "k+1" and you'll get (k+1)*((k+1)+1)/2 which is the same thing as (k+1)*(k+2)/2.
gem