What does mathematical induction really look like? 

A few people have mentioned a subtle mistake in that I should not be saying that for the second (inductive) step we assume our hypothesis for ANY value of n cause that's just what we are trying to prove anyway. But rather we must prove that if it's true for one positive integer n, then it it's true for the next. Just wanted to acknowledge that here, thanks for the correction you guys!

Is this a math channel, an engineering channel or a superposition of the two?

Computer Scienctists: My time has come

Always wanted a better intuition for that

I'm told that to a philosopher, mathematical induction is actually a form of deduction.

I might point out that some of these examples may feel "artificial" to a student, as if specifically tailored to show the power of induction rather than problems that naturally appear in mathematics. But actually, there are many instances in which one needs an induction argument in both "pure" and "applied" maths: for instance in algebra, combinatorics and sometimes in analysis and differential equations (e.g. to find a power series solution Σc_kx^k for an ODE, you inductively find a expression for each c_k in the series). Great video as usual!

Excellent video as always! I know it is subtle, but at 1:46, you SHOULD NOT be assuming the statement is true for any n, because that's what you want to prove, why bother with the rest of the argument if you already assume it's true for any n? What you want, is to prove that for any n, IF the statement works for THAT particular n, THEN it works for n+1 (these statements are not equivalent). Given that you showed it works for n=1, that completes the proof that it works for all n. Induction only works because for any case n+1 you want to check that works, it suffices to reduce it to the previous case n (precisely what your argument does). Any descending chain of natural numbers is finite, so all you need to do is check it works for the first one (in this case n=1) and that's why the rest works. I think this is the most common misconception when it comes to induction. The examples are great by the way :).

While i was watching the video i noticed that all of the inductive argument used in the geometry problems are also valid for 3d versions of these problems. In fact they are valid for any dimensionality. 🤔

"this is probably gonna be the least obvious" *proceeds to show the most obvious* lol

There is tiny bit "error" if I may say: In the method you assume that if it's true for N then that implies being true for N+1, not assume that it's true for N. In the second case you'd be assuming that what you're trying to prove is true, that is a circular argument. Besides that this a very cool visual way of learning, very easier than the way I learned.

Frankly, I found the visual approach more confusing and less convincing than when working just with formulas...

This is very interesting! Thank you, Zach! And again, I am writing this first comment before the video is even published because I'm a patron on Patreon! What an honor! :-)

for the first one shouldnt n = 0 work too? you just need one untiled square (the only square) and no L shape tiles which completes the tiling

Induction is so important and a great visual explanation like this is desperately needed. Thank you Zach!!

In the Hanoi tower example it has been only shown, that it is possible to do with 2^(n-1) steps, but there was no proof, that it is the most efficient way.

Your Tower of Hanoi proof is not complete; it needs a side argument saying you have to make the moves the way you do and that there is not a more efficient way that isn't "move n-1 discs to one peg, move bottom disc, move n-1 discs"

What happens if the "next" line exactly crosses an intersection of the existing lines?

Why not start from a 2⁰×2⁰ grid? That's even easier to show.

Well, this is basically recursion in computer science

Where do you make your animations?

It's a cool introduction but there are a couple of points you missed: 1) you don't always have to start from the smallest n, sometimes n=1,2,3,4 are exceptions, and n=5,6,7,... is where induction can be applied 2) you didn't show strong induction - assuming not only it works for n=k, but for all n=1,2,3,...,k and then proving it works for n=k+1 (aplies to some harder problems) 3) your minimal problem can't be solved by induction - by using induction you find a family of solutions for n=1,2,3,4,.... but if you want minimality you have to show that any solution for n=k+1 has to use a solutionfor n=k. The other thing you can do is show all possible solutions for any n=k+1, only using the solution for n=k and then showing that at the beginning (n=const) you have obvious minimality. Otherwise you're only proving that a solution can not exceed number of moves, therefor a maxima for the problem 4) There are some cases where even/odd numbers matter. You can actually do induction on basis n=1,2 and then prove "if n=k works => n=k+1 works too" 5) There are also some cool examples for multivariable induction. If a=1,b=1 works, and you prove that, given a=m,b=n you have a solution, when having a=m+1,b=n and a=m,b=n+1 it also works, then it works for all (a,b) 6) Induction is really common in graph proofs, so could've included one Anyways, a great video for beginners, would love to see a second part!

1:57 Why not one square? 2⁰×2⁰ with one blank square is just one blank square, which can be tiled with 0 of the L-shaped tiles.

I literally had this problem on an exam and I still have PTSD about it...

Thanks, this was super helpful, keep up the good work!

3:59 you did not tell that by tiling a 2 by 2 grid that way , it implies that we can also tile the 4 by 4 grid also in the same way.............................

Great video I always watch your videos and I recommend these video to my relatives because they are just amazing. I want to ask you ask question about engineering and the question is, which engineering discipline requires the most math while they are on the field. What I mean is what engineering discipline will use the most math when making something related to them, for example, a mechanical engineer making a car engine will he do a lot of math or the computer will do everything for him. Another example Electrical engineering when making satellites and antennas do they use a lot of math or a computer will do everything. Also how hard is the math they are using and from scale 1-10 how do they use. Thank you very much for reading until here, hope u have a wonderful day.

sodoes the first example prove tbat (2^n)^2 -1 is always a multiple of 3?

Where was this when I was learning mathematical induction!?

Thank you man! I think I get this principle now

As a visual learner, I gotta give it to ye! Cheers with the informative and high quality videos of concepts and ideas!

i just understood for the first time, that recursion is closely connected to induction. thanks for that!

I with this existed when I was taking Discrete Math

should we not make n=0 the base case!==1=1=1=1=1=1=1!!!!!!!!!!!

I'm missing something here.. Did try reading a lot of earlier comments, but that didn't help. 1. The "base case " obviously "works" 2. The "n+1" case, where n>=2 , i.e 8x8 or larger, also clearly works, as it's a multiple of the 4x4. 3. But where is it proven that it "works for n", ie n=2, ie that the 4x4 actually works? I mean, i can see that it works... The L shapes can be arranged too "fill" the rest of the 4x4, beyond what the constituent base case holds. But this "check" was not part of the exercise. It is not carried out And, i can sort of "imagine" a situation, with a different problem, where the corresponding n case, ie. corresponding to the 4x4, would not have "worked", but where the multiples of that work, simply because they are just multiple copies of the 4x4, which has been "defined" to work.. Also, to be clear, I don't see why the base case would imply that the 4x4 works. The remainder of the 4x4, excluding the base case, is obviously not a multiple of the base case. But like i said, I'm obviously missing something in the explanation/s given. So, it'd be great with a clarification.

You start with n=1, but I'd like to note that n=0 would be just as good in each case.

thanks .. this was helpful

also do proof by contradiction...

I am wondering if there is a graph-theory proof of the last problem: consider the graph whose vertices are the different regions of the circle and connect them by an edge if the share an side. Is there a simple reason that the graph is bipartite (beside induction)?

My maths book is autistic, it wants you to rewrite the formula with n = p and then do the induction lol. y though :(

So wait.. You're telling me it's possible to beat the tower of Hanoi challenge with any number of disks? 5 is already too hard for me xD

As a math boi I love when you make videos about math

lol the circle colour one was the most obvious to me compared to the previous 2 examples, I proved it myself, and in the other examples I was stumped

Great video ,wish schools could teach like this

Do you have any collection like these examples? because I was fascinated by this and would love to see more such proofs!

My discrete Mathematics prof gave everyone a link to this video, obviously good stuff

I'll be honest. I had figured that tower of Hanoi by myself a few years back by using induction.

Nice video as usual! But a small note: The proof of the first statement doesn‘t quite work as you explained it. It isn‘t sufficient to show, that you can cover all but one square, but you should proof, that you can cover all squares but a square IN A CORNER. That‘s what you use for your induction step, when you split your n+1th square into 4 „n-squares“ and fill the three remaining squares with an L. Otherwise how would you know, that you can fill in the L‘s such that these three squares remain uncovered?

I feel like your first example is slightly wrong because you need to prove that if you can do 2^n*2^n all filled but a corner, you can achieve 2^n+1*2^n+1 all filled but a corner. Having a blank spot in the middle doesn't help. But then if we can easily prove that if you can leave 1 blank space, you can leave any other one blank space, my point is moot. Also the proof still stands because it's easy to show that if you start with a blank corner, you can end with a blank corner.

In the assumption stage you kept saying "assume this holds for Any n". This is in fact incorrect. You assume for a certain n. You treat this n as a constant, particular n and then show that you can infer the n+1 case from it.

You say that is proved yet you didn’t. You need to explain the logic. Nobody could look at this video and think that proves mathematical induction without learning induction somewhere else first. You need to explain the logic properly. Some students may have got something out of this as some extra work because they didn’t understand their class, but this is no prof.

It's been 3 years but I only watched this video now...and wanted to say that as I watched I realized that you can leave a corner out, rotate them to get four empty space in the middle, fill that with another "L shape" and Zach started to do that so I feel very satisfied now.

Regarding the second problem: Not sure if this is trivial, but don't you also need to proove that the quickest way to finish the game is to first move all but one discs on the next rod? Ok ok, after some thinking I see that that's the only way to finish actually.

Nicely done once again! 👍

Just had a test on mathematical induction today at school, I think I did well! But I was curious on how it's applied, so this was a nice watch :)

Similiar to electromagnetical induction, when you pass alternating math through a person's head it will induce mathematic field around that person and alternating math in another person as long as the're close enough.

Am I the only one that was irritated that he didn't lift the Towers of Hanoi rings above the rod holding them in place before moving them sideways?

What you really do is construct a proof for the next value of an iterative taking you through the natural numbers, given a proof for the current value

Nicely presented but I still don't get induction. I don't see how it proves anything.

I’m not sure your Towers of Hanoi proof works as stated. You showed that it *can* be done in 2^n - 1, but not that it cannot be done in less.

i'm completely with you for the jump from 4x4 to any bigger n .. but from the 2x2 to 4x4 no i don't think you even went into proofing it. made the mental gymnastics and yes it works .. but you completly jumped over that .. which is the only real criticism i have on this great video

Proof by contradiction, well ordered principle, existence.

Just in time for my further maths a level.

Where do you make your animations?

Without using induction, prove induction works.

Amazing content. Also, you should consider doing a video about Software Engineering.

I think it was better to collapse the dominos inside out, since inside is finite, aka the 1st case, and outside is the n case

1:43 for *some* n. "For any n" is interpreted as "for all n"

sometimes i speedrun playing hanoi

who saw moving white dots in grid intersections?

This is a pretty subtle mathematical point but when you try to reason "forwards" from n=k to n=k+1, as you do for the lines and circles problem, you have to be careful. What you're trying to prove is "Any circle subdivided by 5 lines" can be colored with only two colors. What you've shown though is that given a circle subdivided by 4 lines with some coloring, you can add another line and get a coloring for a circle subdivided by 5 lines. You haven't yet proven it works for *any* circle subdivided by 5 lines, you need an additional argument that *any* circle subdivided by 5 lines can be constructed by first taking a circle subdivided by 4 lines and adding an additional line. Here it's kind of obvious that this is true, but in general it won't be and you have to take that into account when doing induction. In general the best way to avoid this kind of problem is to *start* with the circle with 5 lines. Then (1) remove one line, (2) show from the inductive hypothesis the circle with 4 lines can be colored, (3) add the line back, (4) prove the coloring for the original 5-line circle is valid. This is analogous to what you did for the squares where the first step was to break a 2^n+1 square into four 2^n squares. If you don't do this step, breaking down the larger problem into smaller sub-problems, then you risk only proving the inductive statement for a subset of cases constructed in a particular way.

tsk, I expected some universal new formula to prove anything via induction... instead of a few examples of induction..

I stumbled upon all those problems with induction in a textbook called "mathematical circles" written by Dmitry Fomin. Is that your source of those problems ?

Hey I am any higher secondry which videos on the channel should I watch? I am new to this channel . Great content btw👍.

Thank you

Looks like a funny game to me.

I got nothing. really nothing

Actually I could see the useful. Although during child education I used number blocks. Brilliant this' still basic algebra & arithmetic. Thanks I am enthusiastic to learn.

That last one also proves any two dimensional shape can be two-colored because any shape can be circumscribed by a circle.

TIL Zach is a fan of Rimmy Tim

you said the last one was the hardest, but I actually looked at it, and in my mind the solution just appeared. edit. and it was the fastest one I did

how did you fill a 4by4? The only way i see is to let one of the center holes be the empty one but then your method for the 16 by 16 wont work.

Not sure why but I often played that two color game in my notebook when I doodled in school

me not getting any of the solutions to the first 2 questions by myself he: now the solution is not very obvious in this one. me: well it is you just gotta draw a segment and invert one side

animation is crazy tho damn

It’s true for all straight lines that run through the circle. Just picture a line perpendicular to the line you just drew, the runs the center point of the circle. It’ll help you if you don’t get it (for the third example).

This implies that 2^(2n) - 1 = 1mod3. Huh.

Should not you have a small detail in the first inductive step? You could fix it by saying: "If we fill a 2^n x 2^n grid with L pieces leaving one of the corners, then we can fill the 2^(n+1) x 2^(n+1), also leaving one of it's corners".

The solution to the first problem is really nice! Damn.

I think I’ve seen that problem from math for comp sci

Discrete Math!!!

The base case here is n=0 which is one tile that will just be left blank.

Hey Zach. Unfortunately, I think you have made a subtle mistake in your inductive step. Sure, you are guaranteed to have one untiled square in every block , but it is not guaranteed to be at a corner. Please tell me if I am wrong!

Marvelous. One of the best visualisation for Mathematical induction.

Wanna know if you really understood the method? Find the mistake in this (obviously wrong) proof: We are going to proof that any set of horses, no matter the set's size, contains only horses whose fur is colored the same color. Base case: If you take a set of one horse, then all (one) horses of that set will trivially have the same color, as there is no other horse that could have a different one. Induction step: Assume this holds for n horses. Then it must also hold for n+1 horses, since if we index each horse from 1 to n+1, then by assumption horses 1 to n have the same color, and so do horses 2 to n+1. This means that horses 1 and n+1 also have the same color, since horse 1 shares a color with horses 2 to n and these share a color with horse n+1. This concludes the proof. Have fun :)

I want to know about mechatronics engineering.

I ratherfound a simple way, we just need to deduct the area of rectangal which is 6... Made by 2 L and at last 4 will be remaining from which we can deduct 3 with is the area of 1 L, ... We can get the number of L 's... Like for 16x16 it will be 85 i. g 256-(3*84)-(3)=1 Where 1 Is the un coverd tile

The proof for the Towers of Hanoi shows only that it is *possible* to solve the game in 2^n - 1 moves. It doesn't imply this is actually the minimum number of moves. (It is, but it doesn't follow from the proof shown).

You assumed 4x4-1 can be covered but you didn't prove it, right? You didn't say it's an exercise left for us, is it?

Thanks

Thanks