Lec 2 | MIT 6.042J Mathematics for Computer Science, Fall 2010

Lecture 2: Induction
Instructor: Tom Leighton
View the complete course: ocw.mit.edu/6-042JF10
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

[@markobisevac2713]

IDK about you, but this is better than Netflix

[@advitiayanand5974]

Can you prove that

[@boboterone9860]

@@codegirl2069 h

[@boboterone9860]

Hgh

[@boboterone9860]

Hgh

[@boboterone9860]

Th h

[@ibramreda728]

time span proof by contradiction 2:30 prove √2 is irrational by contradiction 4:31 False proof example 13:42 induction proofs 20:03 example 1 on induction proof 24:30 example 2 on induction proof 36:37 example on false induction proof 43:34 Example 3 on induction proof 59:00

[@kitkatt6357]

thank u !

[@ayoubfakir1092]

Thanks to all the mathematic professors who helped me hate mathematics over the past years... I'm loving mathematics again :)

[@JimAllen-Persona]

I thought I was the only one… apparently not.

[@buggy_bug]

i didn't hate maths but I didn't liked it either now I'm starting to like it hope I will love it when this course is over

[@3ia13_dianamarsela2]

Oòlp

[@ahmedsameerhassan]

True story

[@VivekRC]

Providing more clarity on the Horse Problem. For the Induction Axiom to work, there are two requirements. 1. Base case must be true - P(1) is trivially true, because the 1 horse will always be the same color as itself. 2. P(n) => P(n+1) - So, when we write n horses, we typically write h(1), h(2), h(3) ....h(n) & for n+1 horses h(1), h(2), h(3) ....h(n), h(n+1) In the above statements, we sub-consciously assume that n is a bigger number greater than 1. Here lies the mistake. Since n can be any number, n can also be 1. So, the list can be: h(n) -----> for n horses h(n), h(n+1) -----> for n+1 horses More specifically: h(1) -----> for n horses, where n being 1 h(1), h(2) -----> for n+1 horses, where n being 1 Now, as per inductive step, predicate is assumed to be true. Assumption: Set of any n horses is of the same color. => h(1) is the same color as itself, say color c1 The assumption also implies that h(2) is the same color of itself, say color c2 Now does h(1) => h(2)? i.e. does c1 = c2? We can't determine that, can we? There is no way we say c1 is always same as c2. So, the inductive step breaks. The takeaway from this problem is to remember the "..." bug that we sub-consciously tend to make. Hope it helps someone :)

[@radiagulzan]

thank you !!

[@emmymatt]

Thank you so much!

[@DavidSanchez-oh2vc]

thanks :)

[@risingredstone5949]

No bruh I think this is incorrect

[@tuanchu8022]

The implication is false when true implies false. Since h(1) is true, and h(2) is true, the implication h(1) => h(2) is true.

[@louislouis117228]

58:20 "So always check the base case. You could prove some great stuff if you don't check the base case." I love this sentence XDDD

[@named161]

This is Awesome!!!

[@user-om7vy6du8t]

Louis Stuck till the end

[@StankyPickle1]

I feel like a wizard when successfully doing a proof by induction!

[@MrAshutoshMohle]

The sound of that chalk pen hitting the blackboard came as pure music to my ears... One who has a love for computers will find this lecture to be a melody. Loved the horse proof...and the tiling problem.

[@zombiesalad2722]

Although its been 3 years since I studied induction in high school, only today I understood why it is true. All thanks to the Indian education system for teaching induction without teaching mathematical logic.

[@Banditxam4]

Yes Bro sams thing happened with me Teacher aya induction ko use kar k math kar dia 2 homework ko de dia kaam khatam 😟😟😟

[@--ShivaS]

yeaaa ritt

[@anuraagrath8876]

IFKR

[@THEMATT222]

69th like

[@sidd6803]

We solve problems without even knowing why the hell we are solving it

[@trippplefive]

Damn....have to use a lot of brain power for this class. I like the approach of this professor where he engages the class, compared to other lazy professors who just read from slides.

[@davidkeys4284]

I love it. The better part of the internet. Challenge us humans.

[@davidkeys4284]

@@benisrood for sure

[@user-om7vy6du8t]

"Brain power"- well seems like you don't enjoy this 😊

[@michaeldick4900]

I love it when the professor writes on the blackboard. It’s like they’re learning it with you. Almost all of my professors are using PowerPoint. :-/

[@NazriB]

Lies again? MRT MIT

[@rahulmathew4970]

Always be vary of the powerpoint

[@deang5622]

Power Point is the lazy man's choice

[@lkopicoghlan9240]

It's really an amazing course! I'm going to study in university next year and i'm coming to look for some inspires for the courses i will take. This outstanding professor do solve a lot of questions for me in advance.

[@mrey845]

With similarity of triangles you can disprove the statement that says "90>92" mentioned at minute 14:43. In the big triangle before splitting in halves, the size of the vertical side is 10 and the horizontal's is 9. After splitting it, the sizes of the small triangles are 2 for the vertical side and unknown for the horizontal, let's call it x. Their angles continue to be consistent, so we can apply similarity: 10/2 = 9/x x = 1.8 So x > 2 is false.

[@KrishNa-hm8mk]

I just realized that the last tile problem was a nicer way of asking to prove that (2^(2*n))-1 is divisible by 3. Love this more verbose way and as well as the story behind it :) Kudos to MIT

[@rkreaden6038]

Damn i just had the realization too

[@jinxerseven]

Great lecture! I am absolutely in love with MIT open course ware.

[@NathanJosephCole]

For the one at the end make an 2^n+1 square out of a 2^n square (one fourth of the field) and the remainder, a 2^(n+1)x2^(n+1) L-shape out of 2^n L-shapes, meaning that each non-two-by-two square can resolve to a smaller square and L-shape where the square is in any quadrant, until you get to the two-by-two which is self-explanatory.

[@georgesadler7830]

Professor Leighton, thank you for a solid introduction to proof by induction. In the early 1990's , I took Advanced Calculus at the University of Maryland College Park and proof by induction was introduced in a slightly different way.

[@samchan2535]

Thank you MIT, for your education.

[@kritisingh3194]

I'm gonna be honest here. I've never really liked giving my time and my efforts to Mathematics. But damn, the way this professor teaches, it's very engaging and very very interesting. Thank you for these materials! These are really helpful.

[@HemmligtNavn]

basis: 2x2 can be tile with a single tile that leaves the NE corner empty. Assume this holds for P(n) now show P(n+1). Split the corresponding 2^nx2^n into 2 regions of size 2^n, apply the induction hypothesis, it gives you that all of these 4 regions can be tiled leaving the NE corner empty. Now simply rotate the NW and SE 2^nx2^n regions 90 and -90 , respectively and you get a L-shaped tile missing in the middle - put a tile here. QED. Now to finish it off, when you have the required size you simply rotate the NE sub square by 180 to get its NE corner to the middle.

[@memoryhero]

This man made induction understandable in the space of 5 mins, where my own prof took 2 hours and left only a classroom full of blank stares. Strong knowledge base != Good teaching!!!

[@guitarman813]

If only my maths lecturer taught like this guy when I was at university...!

[@Kodeekat]

I need proof that such Math profs exist. I think this is CGI....

[@tejeshreddy6252]

Your assumption that this is CGI proves that there is at least one math teacher like him. If not, how would the CGI be made? Boom! Mind = Blown

[@MaybeMisha]

so are you saying dragons exist? orcs exist? all the other crazy things in movies and tv shows exist? CGI is just computer generated graphics - it doesnt have to be based of any real objects.

[@tejeshreddy6252]

Again, flawed. He can be a combination of people if its CGI cuz atleast someone or some people should have thought about making him. Dragons are fictional, yes. But to make a CGI of a real person for one whole lecture with this much perfection surely means that there are people who thought of it. Meaning there are people who know how to explain it. Meaning there is atleast one math professor like him. Please try to think on it for longer. I am not saying he can't be CGI I'm saying his explaining and intellect must be thought by someone else he can't be CGI.

[@MaybeMisha]

Yeah, you're totally right about that, I misunderstood what you meant initially.

[@never_mind_my_comment5044]

For the tile problem, If you have any square missing, the shape of the tiles will not be L For the corner piece missing in 2^n * 2^n, try finding the last piece to be L in shape while leaving a corner empty.

[@whasuklee]

Indeed, fabulous. Learned all the induction from here. Thank you so much!

[@NavalKishoreBarthwal]

killing that pythogarian was quite irrational... :P

[@maximusdizon7267]

get out

[@Banditxam4]

Dude 😬😬

[@muhammadsaimiqbal1551]

I seeee what you did there

[@legacies9041]

Pun intended

[@naziakhan5238]

So, i'm learning from MIT...Thank you ❤

[@donsurlylyte]

this proves to me, it would not have been a good idea for me to go to MIT : (

[@chappie3642]

@@donsurlylyte why not?

[@rajathcumca]

finally i hav no word to say its realy greate lecture thaks sir and thanks MIT

[@hallow6902]

I think it is the consensus among all CS students around the world, that this is the class that's kills us all.

[@prashantsingh1096]

Teaching is art ! Great lecture By Tom Leighton .

[@GtaRockt]

I always thought this proof by induction stuff is like magic. NEVER understood it. But now I do (I think). Great video and thank you for providing it to us for free

[@bhavneetsingh6893]

same here but when he said p(0)->p(1) all came up

[@azizas9366]

proof by induction starts here : 28:31

[@Suamere]

@19:00 The mistake right up-front was not that it was drawn wrong. That is the secondary mistake. The original mistake is that the Height-measure of the original triangles was altered to 8 (with the remainder of 2 added to the sub-triangles) PRIOR to estimating the new base-measure of the sub-triangles. With the correct Height-Measure of 10 and Base-Measure of 9, we don't assume the base is anything-plus. The base is obviously something-minus. But if you first alter the height to 8 with a base of 9, we then assume the base is something-plus, because we forget about the 2 we just removed. So the idea of perception is correct in that it covers up mistakes. But the "right up-front" issue is actually the order of operations, not the sizes of the triangles. The sizes of the triangles are a secondary issue. When I saw the 2+, I wondered why the base of a sub-triangle was different in proportion to the base of the parent-triangle whose base is smaller than its height. The image wasn't the cause of the issue, the order of operations was.

[@kasiditauable]

I thought I lost hope with mathematics. I was kinda slow in my thinking ability. Now I am working towards understanding maths for computer science so that I can go on studying master and eventually PhD. Hope you all enjoy this series of lectures.

[@helixstudio4617]

You got this bro

[@yacinemohammedbahaz2356]

I really admit that I am having an interesting experience with these lessons you offer

[@Yaromiah]

Man, that horse proof was a mindfuck...

[@zooscientist1]

Have you ever followed the horse proof while *high*, man

[@boniike2713]

zooscientist1 you get get

[@boniike2713]

Please call

[@danielfalboyt]

@@zooscientist1 hahahahahahahahahahahahahahahahahahahaha

[@winmarfaulk397]

Amazing professor most people just learn math and know nothing of the history definitely added to my rewatch list

[@peteb345]

Great introduction of inductive proofs. The use of invalid inductive processes is very instructive.

[@EdwinCloud]

What a great teacher

[@roylee3196]

absolutely brilliant class

[@chenchozan8289]

here a 2018 learner pleaseeee keep these videos alive!!! excellent job thank!!!! so

[@buggy_bug]

learning in 2022 and yes it's still alive and very useful to me

[@user-lo4le6jl9b]

well done, thanks for mit offer me such high quality lesson.

[@paraskhosla5640]

In the Horse Problem, does it then mean if we take the predicate to be: P(n): In any set of n>=2 horses, all horses in that set are the same color, then we can establish the truth of the theorem (that all horses are the same color), because then depending on the truth of the base case, we can always establish that P(2)->P(3), P(3)->P(4), ..., P(n)->P(n+1) are true. So that is a bit circumventing around what we actually sought to prove, given that we're assuming that in the base case. Really good problem.

[@tawseeftaher9109]

proof by contradiction 2:30 i.e. root(2) is irrational false proof 13:42 i.e. 90>92 induction 21:00 28:30 prove sum of 1st n natural number = n(n+1)/2 induction q: 37:00 41:45 STEPS OF induction 57:24 ....

[@ExplosiveDiarrheaPig]

I like how when he says: I guarantee you that you'll make a mistake if you use/do X, and then actually makes all the student fall for the trick

[@yb801]

thx,mit,this course really helps

[@tedchirvasiu]

Finally induction is clear... Thanks a ton!

[@Sparklegoat11]

professor explained things simply

[@divyabasuti]

True. Made it easy to understand 🙂

[@arashjamshidi3249]

What a great lecture. Thanks!

[@g0rgth3b0rg]

22:16 is the best explanation of induction in my life.

[@jamaluddin9158]

Indeed!

[@usamanadeem8504]

feeling blessed after joining MIT open courses ;-)

[@FBMachine]

To be more clear, +n - n = 0, so he basically just added 0, which doesn't change the value of the polynomial (which I just incorrectly referred to as an equation). Also, in case you missed it, he didn't just throw in the "-n", he also incremented the 2n (see the change to 3n), which is the +n I was referring to that cancels out the -n, leaving it unchanged.

[@xiaoluo6957]

that 90 > 92 thing really got me... be hold, the splash zone!

[@ayubtes661]

Best professor ever

[@samirfersobe5882]

Awesome lecture.

[@Squ34k3rZ]

On the court yard proof... the base case isn't correct because the statue isn't in the center. It's off to the side in one of the quadrants. It should be partially in all four quadrants to be considered centered...

[@shreydixit2690]

It depends on what 'center' means according to them.

[@fbicitydog5543]

I like watch this it's so very good for my studies

[@Gukslaven]

"If you don't succeed at first, try something harder". Hahaha great quote.

[@geico105]

This actually works believe it or not.

[@shreyanshkushwaha5515]

bill problem can be done this way- well we have a area thats 2^n+1 by 2^n+1 so if we break that up we have 4X (2^n by 2^n) thats the total area since bill had a nice center tile in each of those 4 2^n by 2^n areas hence bill has a center tile in the bigger area made up of 2^n+1 by 2^n+1 and now lets say in case n is 2 this center area is like 2X2 space but we put in another L shaped tile and we have 1 sq left for bill in the center

[@gillakshay]

Thanks, great explanation.

[@sina5an]

This is awesome :)

[@nischallama6707]

sir Time 15:45 , trying to prove 90>92 there in the doted line of a small triangle whose length is 2 is counted in both (small deducted triangle) square length whose length was supposed to be 9-2=7 but counted as 9 by8 AND In that small Deducted triangle whose length and breadth is 2 either you count in (small deducted triangle)real length 9-2=7by8 Or In that small deducted triangle whose length and breadth is 2 by 2

[@dipanshusehjal7305]

In the last proof of 2^n x 2^n tiles, can I make a proposition with "any corner" instead of "anywhere" ? This way I will have a more powerful P(n) without any need of lemma?

[@dondesta4975]

Hello, thank you for all your efforts. I would like to know if the Recitation videos for this class are available to the general public.

[@mitocw]

Sorry there are no recitation videos available for this course but there are recitation notes available. Hopefully they will be of some help. See the course on MIT OpenCourseWare for the materials at ocw.mit.edu/6-042JF10.

[@mokshaagarwal5235]

@@mitocw it is really wonderful how much mit does so that quality education is available to everyone for free.

[@TeDaYMoNgU]

Just this second class completely destroyed my ego. One of the most difficult but stimulating and satisfying classes I've ever engaged myself in; for once I'm truly haunted by what lies ahead.

[@abdikheirosman6795]

I like these staff...

[@nahrafe]

That 90 > 92 thing is kinda sounds like when you divide a 6 by 4 (24 chunks) chocolate and generates 1 more chocolate chunk and rearrange the chocolate back to 6 by 4 and you get 1 extra chunk.

[@anhminhtran7436]

Wow that is a great lecture :)))) I love Discrete Math now

[@stephenoluwafemiherbert]

GREAT WORK

[@Michael13207]

Would it be more specific to say the fallacy-horse-proof fails because the set in which he is applying the induction proof on does not have the inductive property of the natural numbers?

[@jeevanprakash4815]

Very informative. Teachers in my school never explained why we take p(n) => p(n+1) at inductive step.

[@mathematicsfanatic832]

Which school! I'm Indiab Too

[@l3azooka_36]

This really helps me fall asleep thx

[@saket3446]

very helpful lecture

[@amihanov]

I'm a bit lost with "Bill's" problem... Do I need to study matrices properties with powers of 2 ?

[@ilovejingle]

holy shit! why I didnt discover this video when I was in school, it is so intersting and intriguing!

[@easterPole]

@1:01:05 "I'm not supposed to reveal his name so let's call him Bill" LOL

[@1nd93dk3]

And its Bill Gates

[@lukasschmidt2478]

For the set which contains all sets of length n, where all sets of length n+1 has only horses of the same colour, it was not shown that the set of length 1 is a member.

[@karamk92]

hypothesis: any region of " ((2 power n x 2 power n ) - 1) / 3 " is true. Bill will never end up in the center. number of tiles extending away from bill towards opposite ends of any region will always be different ! to center bill and prove L shaped tiles will fit you have to use the hypothesis "((2 power n x 2 power n)-4)/3" is true, base greater than or equal to 1.

[@FBMachine]

He didn't say it wasn't divisible by three, he said it didn't "look" like it was divisible by three. Subtracting n, then adding it back to an equation doesn't change the truth of the equation, so the fact that the rewritten equation was divisible by three proved that (n^3 + 3n^2 + 2n) is divisible by three as well.

[@AbhishekKrSingh-gp4hx]

Proof by induction is great.. I didn't fully grasp the tile problem, but I guess it will come to me by some time..

[@FireSwordOfMagic]

I didn't watch the video, but I wanted to point out that there is a really nice proof for 3|(n^3 - n) that involves modular arithmetic. Simply note that n^3 - n = n(n+1)(n-1) which is clearly 0 mod 3.

[@baslielalene4702]

Thank you.

[@deletedaccount2580]

Motivation : read the comment before watching lecture This will engage you till end of the courses

[@thadeuszl5518]

I don't understand why he said 1:09:25 "We don't want put Bill in the corner, but in the center.". In his initial example with n=2 (1:01:40) he put Bill in the corner as well.

[@jorgevelasco3119]

The tiles are L shaped , the minimum size of area would’ve 4x4 , four L shaped tiles . Then Bill would be in the corner of each L shaped tile but in the center of the 4 L shaped tiles. To me 2 to the n has to be divisible by 4 .

[@ali51717]

"beat me, it doesn't look like a multiple of 3"

[@jonneuro6269]

Ali Abdul-Kareem loves his response to that as well haha

[@mysteryman5582]

Whenever i cant sleep, i watch this video so i can go asleep, thanks math video

[@dreia2405]

At the inductive step, shouldn't be a double arrow between p(n) and p(n+1)? because at the end when you prove that p(n+1) is true that makes the expression p(n) also true

[@mikexia9087]

I wanna to know the reading assignments. There is no information about this on the website of the course. Thx.^ ^

[@mitocw]

The readings can be found in the Readings section of the course website: ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/.

[@LetsBeHuman]

You guys are God. Anyone who provides quality education is God. And that too for free, trust me you are making millions people living in third world countries where education is poor because of bureaucrats, internet is teaching us. THanks a ton. Once you teach us, we know how to fish for rest of our life? And an entire generation will thrive. Thanks a ton. Long live MIT.

[@Reciter_AB]

Is it okay if I didn't understand proof by induction? I mean am I dumb or it's a complex math. Or does it require a previous knowledge of math.

[@94D33M]

Even I didnt understand that much , all I did was that, if you can assume p(n) and show that p(n+1) is also true, then you have proved it

[@joshuamalmberg6091]

Induction can be pretty hard to understand at first. I didn't really understand it for a few years after first studying it. Many people struggle with induction, but with some persistence you can understand it. My advice is to watch some more videos about it until you understsnd how to use it. If it still doesn't make sense to you after watching one video, come back the next day and watch another one. Sleeping on something is really helpful. Once you have learned how to use induction, do some practice problems. Finally, after doing practice problems, watch this video again. Your practical experience will make it much easier to understand the theory behind induction proofs. You can't always learn a difficult concept like induction all at once. But, by chipping away at it over time, you can come to truly understand it.

[@kichuntong4336]

You need the base case to prove everything. The base is, literally, the base. You build from the ground up. When you’ve proved that the ground floor is perfectly done, and you have got the fact that a solid floor would enable you to build a floor on top of it, then you can theoretically construct a building with infinitely many floors. The physical world says such building is not possible, but such thinking is reasonable in the realm of the induction axiom. That’s why the method of induction is an axiom, because it doesn’t apply to everything in the universe, and is chosen according to our purpose.

[@yuancharlie7140]

Best forever

[@gloriasamuel5685]

The Egyptian were the first mathematician not the Greeks. The Greek took the knowledge from the ancient Egyptia. Hence the triangular structure of the pyramids.

[@rozanagrio3252]

Exactly

[@hegelsbagels2006]

I know this is a rudimentary question but what is the distinction between number subscripts, (n and n+1). Are these used synonymously?

[@NavalKishoreBarthwal]

next number in sequence... like arithmetic sequence, geometric sequence or harmonic sequence..... value at nth position and (n+1)th position

[@brontiago]

Horse Problem Clarification: The inductive step doesn’t work when n=1 So P(n) = H1, H2, …, Hn And P(n+1) = H1, H2, …, Hn, Hn+1 1. We assume P(n) is true by induction 2. In P(n+1), we know that the first n horses are the same color because we assumed P(n) is true 3. Now, remove H1 from P(n+1), you’re left with the set {H2, …, Hn, Hn+1}, which now has P(n) horses 4. So now we know that {H2, …, Hn, Hn+1} are all the same color because again P(n) is true 5.(Now here’s the error) The next step WOULD be to say that H1 = {H2, …, Hn} because of step 1 and {H2, …, Hn} = Hn+1 because of step 4, thus implying that P(n+1) are all the same color, BUT look closely at case n = 1: P(1)= H1 P(2) = H1, H2 Remember step 5: H1 = {H2, …, Hn} = Hn+1 But wait, look at the middle set, {H2, …, Hn}. It’s P(n) without H1. Now what is P(1) without H1? *NOTHING, IT’S EMPTY!* Thus saying that H1 is the same color as no horses at all is false, which means step 5 in our induction is false.

[@rebinu]

but then for n>2 suddenly all horses are the same colour?

[@migueldelara9298]

in minute 40:37 , how does adding a -n result in that equation? n^3 + 3n^2 + 2n goes on to be n^3-n+3n^2+3n... after adding -n?

[@MikCish]

Holy shit, these lectures make me mind blow I might have to try and do the readings first and take some time to eat some of these ideas but holy hell

[@makwanabhavin8089]

@58:30 you can prove some great stuff if you don't check the base case.

[@craylixart]

Can someone help me here : In the last problem (bill's), we wanted to prove p(n) but weren't able to do so, so we changed the p(n) and then we proved it . Right? But then we didn't prove it for the original p(n) still?!! So didn't the very proposition we set out to prove still remained unproved?

[@millennia]

can someone please give me a source of which I can find more information about what he said about infinity a being god? at 10:14

[@ahmedsalah5276]

I thought that the bug was in the predicate itself as color is not a function of numbers so how can we make a predicate that you enter a number and it conclude something about colors. I do not know whether this is right or wrong but I guess it makes sense.

[@Alex95334]

For the statue proof, how would one define in mathematical terms the L shape figure of squares used? I proved this is possible using modulo of 3 but it doesn’t specify the shape. Matrice notations maybe?

[@vijy9980]

Hey guys, can't we just nest a square of size 2^n x 2^n on which the inductive hypothesis has been applied in the centre of a square of size 2^(n+1) x 2^(n+1)? In that case, p(n) => p(n+1) right? Meaning every subsequent block up to n+1 will have a bill in the centre.

[@336suryasunkaramech5]

at 56:16, how is that we have proved that proposition for all n>=2?, the equality bridge broke a few minutes earlier....