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!
@@johnny3475 This is true, it's certainly not inductive reasoning (which does not give a "proof" of something). The word is being used in a different sense, but it definitely leads to confusion about the nature of mathematical induction (which is absolutely a form of deductive reasoning).
@@EpicMathTime This is why mathematicians should never be allowed to give names to anything including their own children. They are just horrible. Just look at linear algebra and its orthogonal matrix which consists of orthonormal vectors. Its only called that way because a matrix which consists of orthogonal vectors is of no interest.
@@johnny3475 Because it uses the principle of induction, using the verb induce: to bring about or give rise to. (A much more reasonable use of the word than in inductive reasoning - blame the logicians for that one.)
Logic wise, mathematical proof by induction uses _deductive reasoning_ (and not inductive reasoning!) sure, although the choice of the term “induction” is more that the truth of a statement P(n) for an initial integer value n0 “induces” the truth of the statement for all integers above n0.
It always seemed strange to me to use the word induction for that. In France we use the word "récurrence" instead which makes more sense in my opinion.
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.
Actually, he had it right to begin with other than using N to represent both ANY value of itself as well as ALL values of itself. More on the level of being a typo than a logical error. You are correct that the method is not to assume that a statement N is true, then prove that N⇒N+1 is true and take that as evidence that N is true. That would be circular. The method is to assume that the Kth case of a statement A is true, where A is a statement that is proven in the case of K=1. You use this assumption to prove that A is true in the K+1st case (that is, you prove Aₖ⇒Aₖ₊₁ through mathematical reasoning using the assumption that Aₖ is true). You then take the two proven facts that A₁ and Aₖ⇒Aₖ₊₁ are true to conclude that A₂, A₃, A₄, ... Aₙ are all true. This is not circular reasoning, though it is recursive. You do not assume that Aₖ⇒Aₖ₊₁ is true, you prove it. It is not the assumption of Aₙ (all possible versions of A) that proves Aₙ is true, it is the assumption of Aₖ (Any arbitrary version of A) that proves Aₙ, which is what he said out loud despite using N for everything.
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!
@@DrunkGeko Indeed. May I also give a shout-out to Noetherian induction which is often used in computer science. I like it because it is so elegant. For those who are unfamiliar with it: It is a variant of induction for well-founded relations where you don't need to explicitly prove the base case.
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 :).
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.
It is the most efficient way, think about it At the largest level, it is necessary to move all the smaller disks into one space and leave another empty, moving all the smaller disks is just solving a smaller tower of Hanoi problem. Do this for every step of the way, all the way down to the smallest case, where 1 move is the most efficient solution. Using the same logic as in the video, 2^n - 1 has to be the least number of steps, because at every level of the problem, you are only doing what is necessary to proceed, all the way down to the smallest level, where 1 move is enough.
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 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! :-)
@@mitikox the induction doesn't work, but the solution still does. There's a solution for n=0, and a solution for n=1 that induces the solutions for all n>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.
I've never understood mathematical induction and still don't and I have a BA major in mathematics. I always stumbled on proofs. Needless to say, it affected my grades. I just don't see how any of these examples are proofs.
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.
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!
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.............................
No I didn't explicitly say that and maybe I should've been more formal with that proof but the exact same reasoning as before applies. You can split the 4x4 into 4 quadrants (all of size 2x2) and tile each quadrant such that you can fill in the middle with one more L shaped tile and leave whatever last square untiled.
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).
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)?
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.
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.
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"
This can be considered a trivial lemma, since it is directly implied by the rules of the game: we must somehow move the largest disc to the rightmost pole, and in order to achieve this, we must firstly somehow move the remaining discs to the middle pole. The inductive hypothesis is that moving n discs from the left pole to the middle pole takes (2^n)-1 moves. By the rules, then: in order to move n+1 discs from the left pole to the right pole, we must move n discs from left pole to middle pole, then the largest disc from left pole to right pole, then n discs from middle pole to right pole. There is no way around this.
The crux is this bit: "we must somehow move the largest disc to the rightmost pole, and in order to achieve this, we must firstly somehow move the remaining discs to the middle pole." That's an assumption. It's true, but you have to prove it. Why can't I move, e.g., half the discs to the middle peg, then move the other half to the right peg, and move the discs from the middle peg to the right peg? The answer is I can, but you have to prove that is no more efficient than (and actually equivalent to) your method.
@@klafbang, it is not an assumption; it is a direct implication of the rules. To boot, your example, "move half here, half there, then compose both halves," is precisely a way of moving the whole set to one place. You have not strayed from the rules. As for supposedly needing to prove that no such more efficient method exists: this is not a necessary thing to prove. The formulation of a maximally efficient algorithm is not required in order to derive the proof (though, vice-versa, the formulation of the proof does suggest one such algorithm). The only logical statement made/derived is: "if we can move n discs from one pole to another in no less than 2^n-1 moves, then we can move n+1 discs from one pole to another in no less than 2^(n+1)-1 moves." Proving that moving 1 disc takes 1 move and cannot be done in 0 moves then completes the proof.
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?
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".
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.
It's hard to give specific answers to these questions but it seems aerospace, mechanical, and electrical engineers CAN use a lot of math in their job. That math typically (until maybe you get into research or higher level jobs) isn't super difficult though. For example in my first year as an EE working with antennas I had to convert antenna measurements from one coordinate system to another, I had to use some calculus to make a computer program that calculates errors based on dimensions of the antenna, and I did use euler's formula a few times as we had to deal with sinusoids and phase offsets when working with antenna tracking. School was much more difficult but some of the higher level math was used.
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.
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.
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
You cannot tile a side of a 16x16 square with 3x2 rectangles. If you use 2x3 instead, then you cannot tile it’s adjacent side. The only way would be to put some 2x3 and some 3x2 rectangles, which makes it practically impossible to actually construct.
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.
For hanoi: again, the base case is just [nothing]. Induce: Assume we always can move any tower (x) from one stick to another in 2^x -1 moves. For step k: use 2^k -1 moves to move k rings from the first to the third pole. Use 1 move to move the largest one to the second pole. Use another 2^k -1 moves to move the k stack from the second to the third. The total moves: 2 * 2^k - 2 + 1 = 2^(k+1) -1 to move k+1 rings from any ring to any other
For the circle: Base case, could be nothing (coloring it only orange), but i guess by the requirement it must be 1. Induce: For any circle which has been colored in fewer than three colors, cut it by any line. Invert all colors (from A to B and B to A) on one side of the line. Since there was no conflict before the cut, then by inverting them on one side: that side will not internally conflict (color symmetry), and it will specifically not conflict at the boundary (as every adjacent color has been inverted)
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 ?
Hussein Mohamud I study Actuarial Science , if you do consider Actuarial Science in the future however keep in mind that its not as math heavy as people think, knowledge on Finance and accounting is what will help you more in this degree
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).
I was thinking the same thing. It would also have been nicer if he had started with n=0. This is the true base case, since there are 2^0-1=0 moves required to change 0 disks to another spot.
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.
2:22 - excuse me, but you may have missed the proof of filling the 4x4 square(besides 1 tile) with L-shaped tiles - and just have assumed that this is true. That confused me a little, because proof for the 8x8 case was good enough, but the link with basic case of 2x2 was missing. So I had to apply deduction to prove the 4x4 case.
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.
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
I know this comment is old but maybe there are others wondering: You don't need to prove it for 4x4, that's the point. You prove it for some starting point (2x2 in this case, it could be 1x1 (when n=0) as well), *assume* the hypothesis is true for some constant n (he took 4x4 for visualization but normally you won't set a value for n because it could be any n) and then show that you can conclude the hypothesis is true for n+1 as well, *using* that it is true for n. He showed it is true for 8x8 *if* (assumed) it is true for 4x4. How does this prove it is true for any n (and 4x4 specifically)? Well, you showed it is true for a starting point (2x2) and that you can get from one n (*any* n) to the next. So this means you can get from your starting point 2x2 to the next n (4x4). This also means you can get from 4x4 to 8x8. And from there to 16x16 and so on.
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
@@lc1777 It's a stupid way to prove it. Binomial theorem is trivial. Take (x+y)^n, develop without reducing, you have terms of the form x^i y^(n-i). You have precisely one term of that form for each way of picking i times x and n - i times y among the factors. That number corresponds to the number of ways to take i elements in a set containing n elements, that's n choose i by definition.
Correct, it was the 'inductive step' where we showed that IF it's true then it's true for n+1 (aka the 8x8). Even though formally you don't use a specific case like 4x4 but rather a generic value of 'n'.
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!
For the three blocks where the square is in the corner, remember that he can still tile them however he chooses. He is selecting a solved case from a smaller grid to make it easy to understand and complete. It's only in the FINAL block where the untiled space isn't always in the corner.
The inductive case assumes that for each space in the 2^n size grid, there is a tiling which leaves it empty. In the 2^(n+1) size grid, you can choose at the start any one space to leave empty, which will necessarily be in one of the 4 sections it gets split into. From there, you can choose the tiling which fills that section completely except for the selected space, and with the other three sections make room for the additional tile. This allows the 2^(n+1) size grid to be filled except for any one given space. This can be repeated with all spaces to make a tiling for each. As for the 2x2 case, the L-tile can be rotated any of four ways to leave any given space empty, so therefore you can follow the inductive method to reach a 4x4 tile completely filled except for any given space, and so on.
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 :)
@@merge3550 Almost :) Your intuition that something is fishy with the case of two horses is correct. But what? Horse #n+1 really does have the same color as the horses 2 to n, as horses 2 to n+1 are a set of n horses, which by induction we can assume to be of the same color. The same holds for horses 1 to n. A tip: think about the horses 2 to n for some evil value of n.
Hmm... to me it seems you just stated “If it works for n horses then it works n+1.” But you didn’t prove it. You have to show that for any given set of horses if you add another horse, then that new horse must be the same color.. which is false. You can show by counter example it’s false. Am I getting your point? Or is there more you want to explain with this exercise?
n would be the variable (it's going to take all the values in the domain) p (or 'k' in the texts I've seen) it's just to specify that it's a fixed number. if it's fixed then yo can work with p+1 and things like that. silly, i know, but that's the subtext of the symbols
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!
Zach Star
Great video, but a horrible name for this proof. Mathematical induction is in fact deductive and it’s baffling why someone named it that.
I think the clearest way to present this is to use another letter. We show that "if the claim holds for n = k, then it also holds for n = k + 1".
@@johnny3475 This is true, it's certainly not inductive reasoning (which does not give a "proof" of something). The word is being used in a different sense, but it definitely leads to confusion about the nature of mathematical induction (which is absolutely a form of deductive reasoning).
@@EpicMathTime This is why mathematicians should never be allowed to give names to anything including their own children. They are just horrible. Just look at linear algebra and its orthogonal matrix which consists of orthonormal vectors. Its only called that way because a matrix which consists of orthogonal vectors is of no interest.
@@johnny3475 Because it uses the principle of induction, using the verb induce: to bring about or give rise to. (A much more reasonable use of the word than in inductive reasoning - blame the logicians for that one.)
Is this a math channel, an engineering channel or a superposition of the two?
Often ,but not always, it's math used in engineering (or some other applied field), so could say a superposition lol.
Neeeeerds
It's a dank ass channel.
@@pipertripp of all the ass channels, this one is the dankest.
@@zachstar is there a book with tasks of this type?
Always wanted a better intuition for that
Computer Scienctists: My time has come
*recursion intensifies*
@@Andrew90046zero *recursion intensifies*
@@franchufranchu119 *recursion intensifies*
@@sqoob7082 Stack overflow
@@Phroggster someone always has to be the final condition
I'm told that to a philosopher, mathematical induction is actually a form of deduction.
Logic wise, mathematical proof by induction uses _deductive reasoning_ (and not inductive reasoning!) sure, although the choice of the term “induction” is more that the truth of a statement P(n) for an initial integer value n0 “induces” the truth of the statement for all integers above n0.
It always seemed strange to me to use the word induction for that. In France we use the word "récurrence" instead which makes more sense in my opinion.
Induction is so important and a great visual explanation like this is desperately needed. Thank you Zach!!
Thanks for the comment Chris!
Zach Star always my pleasure!
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.
Yes thanks for the correction!
Ex falso sequitur quodlibet.
He proved that it was true for one N, N=1 (one piece takes one move)
Actually, he had it right to begin with other than using N to represent both ANY value of itself as well as ALL values of itself. More on the level of being a typo than a logical error.
You are correct that the method is not to assume that a statement N is true, then prove that N⇒N+1 is true and take that as evidence that N is true. That would be circular.
The method is to assume that the Kth case of a statement A is true, where A is a statement that is proven in the case of K=1. You use this assumption to prove that A is true in the K+1st case (that is, you prove Aₖ⇒Aₖ₊₁ through mathematical reasoning using the assumption that Aₖ is true). You then take the two proven facts that A₁ and Aₖ⇒Aₖ₊₁ are true to conclude that A₂, A₃, A₄, ... Aₙ are all true. This is not circular reasoning, though it is recursive.
You do not assume that Aₖ⇒Aₖ₊₁ is true, you prove it. It is not the assumption of Aₙ (all possible versions of A) that proves Aₙ is true, it is the assumption of Aₖ (Any arbitrary version of A) that proves Aₙ, which is what he said out loud despite using N for everything.
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!
Also, induction is crazy powerful in computer science as most algorithms can be proven to be correct thanks to it
@@DrunkGeko Indeed. May I also give a shout-out to Noetherian induction which is often used in computer science. I like it because it is so elegant. For those who are unfamiliar with it: It is a variant of induction for well-founded relations where you don't need to explicitly prove the base case.
Yep
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 :).
Thank you, I knew something was wrong with that statement but couldn't give remember what.
Yes thanks for that correction! Just pinned a comment about that.
thank you! i was searching for this
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.
It is the most efficient way, think about it
At the largest level, it is necessary to move all the smaller disks into one space and leave another empty,
moving all the smaller disks is just solving a smaller tower of Hanoi problem. Do this for every step of the way, all the way down to the smallest case, where 1 move is the most efficient solution.
Using the same logic as in the video, 2^n - 1 has to be the least number of steps, because at every level of the problem, you are only doing what is necessary to proceed, all the way down to the smallest level, where 1 move is enough.
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. 🤔
Yeah man, induction has very broad applications. In a way it basically is just.. the "elemental" form of recursion?
@@phatkin 😀
@pyropulse How is anything about non-Euclidean geometry implied?
@pyropulse Error : does not compute. Need more citations 😵
@@phatkin the shorter summary is that recursion is induction.
Thanks, this was super helpful, keep up the good work!
As a visual learner, I gotta give it to ye! Cheers with the informative and high quality videos of concepts and ideas!
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! :-)
So thats how people do it...
@@leg10n68 yeah!!😮
@@leg10n68 Yep! You can support too. One-two dollars per month is not a big deal!
i just understood for the first time, that recursion is closely connected to induction. thanks for that!
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
Harder to visualize, the way he did it is way simpler.
Yup, that works too.
The induction wouldn't work from n=0 to n=1
@@mitikox it does, in a really weird, hard to explain to a broader audience way
@@mitikox the induction doesn't work, but the solution still does. There's a solution for n=0, and a solution for n=1 that induces the solutions for all n>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.
I've never understood mathematical induction and still don't and I have a BA major in mathematics. I always stumbled on proofs. Needless to say, it affected my grades. I just don't see how any of these examples are proofs.
Nicely done once again! 👍
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.
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.
You'd still need to prove with n=1 as another base case as the induction step from n=0 to n=1 doesn't really work
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!
Thank you man! I think I get this principle now
"this is probably gonna be the least obvious"
*proceeds to show the most obvious* lol
I literally had this problem on an exam and I still have PTSD about it...
Why not start from a 2⁰×2⁰ grid? That's even easier to show.
What happens if the "next" line exactly crosses an intersection of the existing lines?
It works the same way with the same explanation.
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.............................
No I didn't explicitly say that and maybe I should've been more formal with that proof but the exact same reasoning as before applies. You can split the 4x4 into 4 quadrants (all of size 2x2) and tile each quadrant such that you can fill in the middle with one more L shaped tile and leave whatever last square untiled.
Well, this is basically recursion in computer science
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 :)
Where was this when I was learning mathematical induction!?
Marvelous. One of the best visualisation for Mathematical induction.
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).
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)?
The corresponding planar graph has no cycles of odd length.
thanks .. this was helpful
This was beautiful. Thank you!
Great video ,wish schools could teach like this
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.
Do you have any collection like these examples? because I was fascinated by this and would love to see more such proofs!
As a math boi I love when you make videos about math
much more interesting than doing integarahls at school
sodoes the first example prove tbat (2^n)^2 -1 is always a multiple of 3?
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.
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
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"
scrolled for this
That's not what he said; he said the goal was to prove it requires a minimum of 2^n-1 moves (which is correct but not proven here).
This can be considered a trivial lemma, since it is directly implied by the rules of the game: we must somehow move the largest disc to the rightmost pole, and in order to achieve this, we must firstly somehow move the remaining discs to the middle pole. The inductive hypothesis is that moving n discs from the left pole to the middle pole takes (2^n)-1 moves.
By the rules, then: in order to move n+1 discs from the left pole to the right pole, we must move n discs from left pole to middle pole, then the largest disc from left pole to right pole, then n discs from middle pole to right pole. There is no way around this.
The crux is this bit: "we must somehow move the largest disc to the rightmost pole, and in order to achieve this, we must firstly somehow move the remaining discs to the middle pole." That's an assumption. It's true, but you have to prove it. Why can't I move, e.g., half the discs to the middle peg, then move the other half to the right peg, and move the discs from the middle peg to the right peg? The answer is I can, but you have to prove that is no more efficient than (and actually equivalent to) your method.
@@klafbang, it is not an assumption; it is a direct implication of the rules. To boot, your example, "move half here, half there, then compose both halves," is precisely a way of moving the whole set to one place. You have not strayed from the rules.
As for supposedly needing to prove that no such more efficient method exists: this is not a necessary thing to prove. The formulation of a maximally efficient algorithm is not required in order to derive the proof (though, vice-versa, the formulation of the proof does suggest one such algorithm). The only logical statement made/derived is: "if we can move n discs from one pole to another in no less than 2^n-1 moves, then we can move n+1 discs from one pole to another in no less than 2^(n+1)-1 moves." Proving that moving 1 disc takes 1 move and cannot be done in 0 moves then completes the proof.
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?
Well the assumption was that it could work for any square.. so that would include the ones in the corner!
Woops i misunderstood that, thx :)
The base case here is n=0 which is one tile that will just be left blank.
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".
@@pineberryfox Okay. That works.
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.
It's hard to give specific answers to these questions but it seems aerospace, mechanical, and electrical engineers CAN use a lot of math in their job. That math typically (until maybe you get into research or higher level jobs) isn't super difficult though. For example in my first year as an EE working with antennas I had to convert antenna measurements from one coordinate system to another, I had to use some calculus to make a computer program that calculates errors based on dimensions of the antenna, and I did use euler's formula a few times as we had to deal with sinusoids and phase offsets when working with antenna tracking. School was much more difficult but some of the higher level math was used.
He also has a video about how much math engineers typically use on the field.
@@zachstar Thank you sooo much for your reply, it really helped
@@andraskovacs6403 I am surprised I never came across that video,but thank you for making me aware of it, appreciate it
You start with n=1, but I'd like to note that n=0 would be just as good in each case.
The solution to the first problem is really nice! Damn.
1:43 for *some* n. "For any n" is interpreted as "for all n"
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.
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'll be honest. I had figured that tower of Hanoi by myself a few years back by using induction.
Woah. You are so random ☺
Brutally Honest®
Hey I am any higher secondry which videos on the channel should I watch?
I am new to this channel .
Great content btw👍.
That last one also proves any two dimensional shape can be two-colored because any shape can be circumscribed by a circle.
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.
Frankly, I found the visual approach more confusing and less convincing than when working just with formulas...
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.
Not sure why but I often played that two color game in my notebook when I doodled in school
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.
really liked the two color example
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
You cannot tile a side of a 16x16 square with 3x2 rectangles. If you use 2x3 instead, then you cannot tile it’s adjacent side. The only way would be to put some 2x3 and some 3x2 rectangles, which makes it practically impossible to actually construct.
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.
For hanoi: again, the base case is just [nothing]. Induce: Assume we always can move any tower (x) from one stick to another in 2^x -1 moves. For step k: use 2^k -1 moves to move k rings from the first to the third pole. Use 1 move to move the largest one to the second pole. Use another 2^k -1 moves to move the k stack from the second to the third. The total moves: 2 * 2^k - 2 + 1 = 2^(k+1) -1 to move k+1 rings from any ring to any other
For the circle: Base case, could be nothing (coloring it only orange), but i guess by the requirement it must be 1. Induce: For any circle which has been colored in fewer than three colors, cut it by any line. Invert all colors (from A to B and B to A) on one side of the line. Since there was no conflict before the cut, then by inverting them on one side: that side will not internally conflict (color symmetry), and it will specifically not conflict at the boundary (as every adjacent color has been inverted)
My discrete Mathematics prof gave everyone a link to this video, obviously good stuff
I with this existed when I was taking Discrete Math
Where do you make your animations?
Amazing content. Also, you should consider doing a video about Software Engineering.
Already has one jus look for it
@@levibeam100 Thanks. I have found it.
is it allowed to move more than one disk at the same time in the tower game ?
no just one at a time.
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
Yes, Exists a repetition algorithm that even a human can do easily, and can solve any number of disks.
The original puzzle is 64 disks. And yes, it's possible.
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
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 ?
Just in time for my further maths a level.
Badman well im doing as first(yr 12)
Good luck to you, btw I got an A for FM hehe
Yuan Zhi Lee
Wait, do you go to uni and if so what do you study?
Hussein Mohamud I study Actuarial Science , if you do consider Actuarial Science in the future however keep in mind that its not as math heavy as people think, knowledge on Finance and accounting is what will help you more in this degree
Thank you
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).
I was thinking the same thing. It would also have been nicer if he had started with n=0. This is the true base case, since there are 2^0-1=0 moves required to change 0 disks to another spot.
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.
2:22 - excuse me, but you may have missed the proof of filling the 4x4 square(besides 1 tile) with L-shaped tiles - and just have assumed that this is true. That confused me a little, because proof for the 8x8 case was good enough, but the link with basic case of 2x2 was missing.
So I had to apply deduction to prove the 4x4 case.
should we not make n=0 the base case!==1=1=1=1=1=1=1!!!!!!!!!!!
also do proof by contradiction...
they are somewhat same
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.
Very nice video
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
im wondering that too, how did he prove it for the 4x4... :s
I know this comment is old but maybe there are others wondering: You don't need to prove it for 4x4, that's the point. You prove it for some starting point (2x2 in this case, it could be 1x1 (when n=0) as well), *assume* the hypothesis is true for some constant n (he took 4x4 for visualization but normally you won't set a value for n because it could be any n) and then show that you can conclude the hypothesis is true for n+1 as well, *using* that it is true for n. He showed it is true for 8x8 *if* (assumed) it is true for 4x4.
How does this prove it is true for any n (and 4x4 specifically)? Well, you showed it is true for a starting point (2x2) and that you can get from one n (*any* n) to the next. So this means you can get from your starting point 2x2 to the next n (4x4). This also means you can get from 4x4 to 8x8. And from there to 16x16 and so on.
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
Very neat!
I think I’ve seen that problem from math for comp sci
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
The disk moving is basically like binary counting
I learned that from 3b1b
I want to know about mechatronics engineering.
Silly question here: is this something that one would find in a proof class? This sort of math feels pretty alien to me
Yep! A first course in proofs usually has induction.
It's easier to prove many theorems especially binomial theorem and problems in number theory
@@srinivaspai3911 lmao you prove the binomial theorem by induction? 😂
@@randomsoul294 um what's wrong with that?
@@lc1777 It's a stupid way to prove it. Binomial theorem is trivial.
Take (x+y)^n, develop without reducing, you have terms of the form x^i y^(n-i). You have precisely one term of that form for each way of picking i times x and n - i times y among the factors. That number corresponds to the number of ways to take i elements in a set containing n elements, that's n choose i by definition.
animation is crazy tho damn
Math is a beautiful form of art...
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?
Thanks
who saw moving white dots in grid intersections?
sometimes i speedrun playing hanoi
Proof by contradiction, well ordered principle, existence.
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?
Correct, it was the 'inductive step' where we showed that IF it's true then it's true for n+1 (aka the 8x8). Even though formally you don't use a specific case like 4x4 but rather a generic value of 'n'.
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!
For the three blocks where the square is in the corner, remember that he can still tile them however he chooses. He is selecting a solved case from a smaller grid to make it easy to understand and complete. It's only in the FINAL block where the untiled space isn't always in the corner.
The inductive case assumes that for each space in the 2^n size grid, there is a tiling which leaves it empty. In the 2^(n+1) size grid, you can choose at the start any one space to leave empty, which will necessarily be in one of the 4 sections it gets split into. From there, you can choose the tiling which fills that section completely except for the selected space, and with the other three sections make room for the additional tile. This allows the 2^(n+1) size grid to be filled except for any one given space. This can be repeated with all spaces to make a tiling for each.
As for the 2x2 case, the L-tile can be rotated any of four ways to leave any given space empty, so therefore you can follow the inductive method to reach a 4x4 tile completely filled except for any given space, and so on.
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 :)
@@merge3550 Almost :)
Your intuition that something is fishy with the case of two horses is correct. But what?
Horse #n+1 really does have the same color as the horses 2 to n, as horses 2 to n+1 are a set of n horses, which by induction we can assume to be of the same color. The same holds for horses 1 to n. A tip: think about the horses 2 to n for some evil value of n.
Hmm... to me it seems you just stated “If it works for n horses then it works n+1.” But you didn’t prove it. You have to show that for any given set of horses if you add another horse, then that new horse must be the same color.. which is false. You can show by counter example it’s false. Am I getting your point? Or is there more you want to explain with this exercise?
My maths book is autistic, it wants you to rewrite the formula with n = p and then do the induction lol. y though :(
n would be the variable (it's going to take all the values in the domain)
p (or 'k' in the texts I've seen) it's just to specify that it's a fixed number. if it's fixed then yo can work with p+1 and things like that.
silly, i know, but that's the subtext of the symbols
Wow required that