MATHEMATICAL INDUCTION - DISCRETE MATHEMATICS

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 KZbin: 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.

[@jonathanharris2326]

How many CS students are watching these vids?

[@mohamedfathy002]

69 cs students XD

[@filspyrospapabundus]

Brazil

[@monavie9110]

@@filspyrospapabundus lol

[@filspyrospapabundus]

@@monavie9110 lol

[@jonathanharris2326]

@Bryant Shiloh No, no one cares. Totally fucking stupid to post this on a mathematical induction lecture video.

[@Fuckingcoward]

good luck to all CS students watchin this. LET'S GET THIS DEGREE AND CLAIM THE BAG!

[@atharvab.3342]

2:50 format 4:05 first example 8:57 first example solution 9:05 second example 12:44 second example solution

[@augusteine1089]

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

[@FelipeBalbi]

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

[@yusram.6175]

where does the 2 come from in the first?

[@alexisluna788]

​@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

[@zheite5154]

Thanks, was doubting myself at first lol

[@Marnige]

@@FelipeBalbi you couldve just took out common term (k+1) to instantly get (k+1)(k+2(1))

[@stovegamesgames6917]

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."

[@KixSoso]

which book is this?

[@vedkorla300]

@@KixSoso Kenneth Rosen DMGT

[@countbrackmoor]

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.

[@arhamkhawar4240]

Thanks, this really helped.

[@ridovercascade4551]

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.

[@UnfinishedYara]

We've all been there man lol

[@mamunrashid9577]

@@ridovercascade4551 U r funny

[@ridovercascade4551]

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.

[@Johnathanaa7]

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)

[@glennredwine289]

You guys are so.lucky that you have this KZbin 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.

[@xeon39688]

@@glennredwine289 true

[@user-ti7me6yv7w]

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.

[@ghadaalmousa8505]

I totally understand NOTHING !! i hate this chapter...

[@socratears]

i feels u bro

[@RoganPlant]

same

[@fsx99]

:(

[@MDArif-xy5cc]

but it is really easy when you understand clear concept

[@user-qc5jw1xy5l]

@@MDArif-xy5cc stfu

[@dayrontabares4757]

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 :)

[@LOORTIX]

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!

[@bearboyjd5394]

Thank you so much for this, my teacher is a joke and this video just saved me about 3 hours of headaches.

[@MaceOjala]

I've never heard induction explained like this, thanks.

[@MaceOjala]

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

[@Trevtutor]

+Mace Ojala Sometimes it just takes a different style of teaching to help. Glad you're enjoying it.

[@MaceOjala]

That's right. Plus >20 years of time and life experience in other areas makes a difference too, I bet.

[@jumaelahmed9995]

@@TrevtutorEnjoying!

[@NazifaTasneemchesirecat]

Discrete is so annoying

[@kurokatana101]

I might survive discrete math yet thanks to you!

[@mouadrimwind8839]

did you survive ? asking for a friend xD

[@rishanaaishath8211]

@@mouadrimwind8839 did you survive? Asking for my grandma

[@mouadrimwind8839]

@@rishanaaishath8211 passed with C+ Lowest grade in my transcript so far but I did pass ouff

[@glennredwine289]

@@mouadrimwind8839 JUST SO MUCH GARBAGE!!

[@centralpalace2314]

i did not survive, failing an exam as we speak

[@ColdFuse96]

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)?

[@scottwitoff8932]

This guy needs to be inducted into the hall of fame for math instructors

[@joelbny]

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.

[@kennu3988]

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.

[@cpoppinz12]

Do you have any videos on strong induction and recursion?

[@stanislavmodrak3142]

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

[@SomeGuy5009]

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.

[@lexxless831]

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.

[@ultrastudy8224]

I took discrete math years ago and this video helped sooo much! You are the man!

[@idkaname1539]

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!

[@shazrylhakeemy8972]

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

[@gabrielmoreno3027]

how'd it go? likely failed...

[@garveziukas]

You better explain the subject in first 2 minutes than my discrete math professor does in 2 x 1,5h lectures

[@h_githma]

Your videos are the best! Watching this b4 exams tomorrow

[@Epic-so3ek]

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.

[@ghazalshall9367]

i cannot understand a thingggggg

[@Samastano]

That's the most important part. Is for something to hold forever... *cries in math*

[@gideonadzasu5109]

how did you get the (k+2) in the second step ???

[@miriamDev]

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

[@Taziod]

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

[@ReemReem-nv6mk]

+Taziod I don't understand where did the 2 in (k(k+1)+ 2 *(k+1))/2 come from ???

[@chunkdouglas4425]

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.

[@connorburgess4894]

so what you're saying is he's wrong right Chunk?

[@dbf72829]

@Edwin Kaburu yep

[@debonairrose]

haaah 12:14 "Ass."

[@PsXboxGamerTrollPro]

Thank you, video was really helpful and everything was explained really clearly!

[@joseg5287]

Thank you. I am studying for my cset, this helped out alot.

[@kristinetagnipez317]

thank u very much!!! wish me luck on my exams 😊😊

[@abdulmalikjahar-al-buhairi9754]

Hmm weird we never do it with n

[@VGx7]

At 7:30 you change it to 2(K+1) why is that?

[@kirankumar-ki3ci]

coz 2(k+1)/2 =(k+1) itself,the reason he did is to get same denominator in LHS as RHS

[@DingleBerrieLol]

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

[@SidTech7.0]

Pls help me solve this one its been giving me a headache Prove by mathematical induction that n(n+1)(n+5) is a multiple of 3 for all n is an element of natural numbers(n€N)

[@aaronthompson144]

The other video is here: kzbin.info/www/bejne/nKOXpHWJZ61moJY

[@wm78965kidtips]

why did you use N

[@lowellwb]

i agree... i also wonder why?

[@amirul264]

k is a constant, while n is not.

[@JoffreyB]

because it doesn't matter. It's the same meaning.

[@marcuskolade703]

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.

[@tyrt400z]

because if he didn't do n

[@jadeshinymist1639]

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)?

[@michaelknapp454]

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.

[@danielcohenemail]

why do we assume n

[@gabe_owner]

It means that K is bigger than N, so you can regress back to the base case after K-N applications.

[@Taziod]

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.

[@Trevtutor]

+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.

[@toko2519]

5:26 doesn’t make sense. Where is k+2 coming from ? Shouldn’t it be (k+1)(k+1)

[@nateromo1234]

it could be written (k+1)((k+1)+1) since both k's are replaced with k+1, this can be simplified to (k+1)(k+2) since 1+1=2

[@obaapakusi4844]

Thank you.Your videos are the best

[@Mr.camaron8]

Trying to clutch. Wish me luck

[@ratdog356]

howd it go

[@nathanielohiare5717]

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

[@jakobjensen8228]

This video is on my syllabus

[@duksy5700]

Man I love discrete math it’s so damn interesting

[@itumelenghuma1959]

This is a very good video. Thank you.

[@svampyr7964]

I have a problem here prof n^4 < 4^n, for n> 4, would you help me with this one?

[@TKSlowah]

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.

[@pial2461]

It would be better if you took recurrence relations as an example for the "Induction Proof". Anyway gold content!

[@Dante-ot8xg]

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?

[@domicio1577]

Why should I use this in practice? Maybe to prove my algorithm holds true to any random value?

[@sarvinozpardaeva3168]

Thank you very much. I really love your videos. You are the best)))

[@darkdudironaji]

I paused the video at 7:15 and was scratching my head at how k(k+1)+(k+1) was supposed to be (k+1)(k+2). I kept getting (k+1)^2. I shoulda just let the video play another 10 seconds.

[@amorfati4559]

Thanks a lot man. That really helped me out.

[@afifahsabirah9233]

I loveee your handwriting!!! 💕💕💕

[@anty.]

hi i know this is 9 years old but how did you get the k(k+1) + 2(k+1) at 7:30

[@darius5392]

i wish he had edited out the errors at abt 8 mins it made everything thereafter confusing as hell

[@jumaelahmed9995]

best teacher!

[@LearnersVault]

Thank you for this video. But can you explain strong induction please. Thank you.

[@luthfiidrus5188]

this video really helped me. thank you so much

[@dbf72829]

Same lol

[@logandanger]

Thank you.

[@II_xD_II]

Hey can you add Strong mathematical induction ??

[@vortrusofficial8034]

Thank you! Thank you SO MUCH!

[@stmobile453]

I don't understand at 5:32 when he said he just used k+1 per k to generate (k+1)(k+2)/2

[@rainorchid11]

how do you know what to choose for your base case for any given problem? what is the strategy for choosing the base case?

[@glennredwine289]

rainorchid1 You always start with 1, n=1.

[@Zulfurin]

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?

[@Trevtutor]

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.

[@Zulfurin]

@@Trevtutor That makes sense, thank you!

[@christophernaron2828]

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.

[@Trevtutor]

+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.

[@RedQueenAvenged]

+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.

[@stevo946]

+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

[@ast3077]

+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.

[@samuelchristophervisarra7830]

@@RedQueenAvenged but that's not what happened, right?

[@omomohomegie3570]

Pls can you make another video explaining the last proof you just explained in this video???

[@weggquiz]

well understood

[@ZuestTV]

simply amazing keep on the great work!!!

[@craig7878]

where did the (k+1)(k+2) come from?

[@evev6383]

Where did the k+2 come from in the first example though?

[@17noMad17]

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.

[@icaruswong1]

Thank you kind sir

[@lukeketterer]

Can someone explain to me why we do +2(k + 1) around the 7:30 mark. I'm not great with algebra

[@devkunjadia3792]

Great video

[@hammo7406]

amazing explenation

[@amazongadgetsmaster1545]

Using mathematical induction, prove that 1? + 2? + 3? +..... + n? = (1/6){n (n + 1) (2n + 1)} for all n ? N.

[@MegaMetang]

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.

[@oldtvnewguy2727]

thanks for the help

[@LIAQATALI-cf1gg]

Good work. Thanks

[@lowellwb]

why did you use n< or = k , not n> or = k? Aren't we using natural numbers? means > or = 1

[@Trevtutor]

n =1, so we can't assume it.

[@dubeya01]

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?

[@Trevtutor]

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.

[@hazbean6125]

Thanks soooo much!

[@gackerman99]

Is it not the case that you can't JUST assume that k is true, then show that k=1 is true, and be done with it? At some point you have to show that k is concretely true (i.e. what you did in showing the base case). That seems really important and probably a source of a lot of confusion because you're emphasizing this "assumption" so much it sounds like we're allowed to take it for granted, which would allow us to prove all sorts of insane and evidently wrong things.

[@hawgrider44]

High quality video

[@basantallam7757]

that was so useful!

[@ayushbhuwalka2022]

thanks bro

[@mr.capturing8390]

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?

[@tomashaddad]

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?

[@satyaprakashsoren5986]

well explained sir

[@g.atharva9174]

ELON IS TEACHING US !

[@goodmusic284]

Thank you!

[@pial2461]

really cool! Discrete math is the coolest thing ever! specifically the proofs. It really helps us to understand the world with mathematical perspective.