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!

Always wanted a better intuition for that

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

Computer Scienctists: My time has come

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!

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.

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

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

Excellent video as always! I know it is subtle, but at <a href="#" class="seekto" data-time="106">1:46</a>, 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 :).

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.

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

Nicely done once again! 👍

This was beautiful. Thank you!

Marvelous. One of the best visualisation for Mathematical induction.

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!

thanks .. this was helpful

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!

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

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

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.

Thank you man! I think I get this principle now

Great video ,wish schools could teach like this

Where do you make your animations?

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

The solution to the first problem is really nice! 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).

Thank you

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.

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

Very neat!

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

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

Where was this when I was learning mathematical induction!?

Very nice video

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

really liked the two color example

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

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

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.

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.

<a href="#" class="seekto" data-time="117">1:57</a> 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.

Thanks

Well, this is basically recursion in computer science

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

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

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

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.

<a href="#" class="seekto" data-time="239">3:59</a> 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.............................

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

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

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

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"

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

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

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

I with this existed when I was taking Discrete Math

Wow required that

animation is crazy tho damn

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?

is it allowed to move more than one disk at the same time in the tower game ?

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.

<a href="#" class="seekto" data-time="103">1:43</a> for *some* n. "For any n" is interpreted as "for all n"

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

reminds me of a MIT lecture

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

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.

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

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

also do proof by contradiction...

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

For the first problem: You can actually start at N=0, so there's no initial step (only induction!) Induce: Assume we always leave the bottom-right corner empty of a step N=k. Copy the solution to step k-1 four times, arranged in a square. Rotate the top right and bottom left to face their unfilled corners to the center. Now there are three adjacent unfilled tiles, arranged in an L shape; fill it with the L piece. The result leaves one open square in the bottom right.

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.

Just in time for my further maths a level.

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

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.

Woah

The disk moving is basically like binary counting

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

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 ?

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

Math is a beautiful form of art...

Proof by contradiction, well ordered principle, existence.

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

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

Looks like a funny game to me.

wow

cool

I want to know about mechatronics engineering.

TIL Zach is a fan of Rimmy Tim

Silly question here: is this something that one would find in a proof class? This sort of math feels pretty alien to me

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?

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

Susanne epp?

sometimes i speedrun playing hanoi

who saw moving white dots in grid intersections?