[MUSIC] Hi, I'm Michael Levin and in this lesson we're going to study mathematical induction. It is a very powerful proof method. It is very similar to this example with falling dominos. You know that if we put many, many dominos on the floor, so that the second domino is right in front of the first one, and the third one is right in front of the second one, and so on. And then we push the first domino, it will fall, and it will push the second one in front of it. And that domino will also fall and it will push the third one and so on and then all the dominos will actually fall. And we can check that for maybe 1 domino, 2 dominos, maybe 5, 100, or 1,000. But how to prove that for any number of dominos. It seems obvious from your practical life experience. But actually to prove that strictly that even a million dominos will fall, we will have to think about what happens in the general case. So we know that if we push the first domino it will fall. And also what we know is that if some domino on position k falls, it will push forward the k plus first domino and that one will also fall. And from that, we can conclude that if we push the first one, then any domino in the row even one thousands and even the one millionth, all of them will fall. And mathematical induction is a proof method which is based on the same principle. And there are a lot of problems, hard problems, which can be proven only using these kinds of methods like mathematical induction. And many computer science algorithms are actually proven using induction. And we'll start with an example of lines and triangles. We will consider the following problem. Several straight lines are drawn on a plane, and in a sense they cut this infinite plane into pieces. And you can see an example on the picture. We have four lines there and we have many, many pieces between segments of those lines. Some of those pieces are infinite ,and some of those pieces are finite. And we'll require that each line intersects with every other line. So there are no parallel lines. And also all the intersection points are different so that no three lines intersect in the same point. And what we want to prove is that there must be at least one triangle piece. In this picture, we actually see two triangle pieces. The one below and the one above. And we state that, if all the conditions are met, if every two lines intersect and there are no points where at least three lines intersect, then there always will be at least one triangle piece. So how to prove this statement. Well we have the following idea, as soon as there are three lines, we know that those three lines cannot intersect in one point. And from that it immediately follows that if there are exactly three lines, we'll have a triangular piece formed by those three lines. And then, if we have more lines, then we can actually imagine that we have first only three lines. Some of those lines we have, some three first lines and we can chose them arbitrarily. And then we are going to add more lines one by one. And when we add more lines one by one, every time either the same triangle piece that already existed before adding that line remains, if that line doesn't touch this piece and it remains intact, or a new triangle appears. And this is the general idea. So we start with three lines and we immediately get a triangle. And then when we add more line, either it doesn't touch this piece and the triangle remains or a new one appears. Let's see how that happens. So when we have just three lines, in the general position they form a triangle because each of them intersects another one, and we have three points of intersection, and we require that those three points are different. And so those three points, together with those lines form a triangle, which is highlighted with orange here. So, there is a bad case where there is no triangle, but in this case we have this common point of intersection of three lines which is what we forbid. So, this cannot actually happen in our problem statement because we forbid three lines intersecting the same point. So this can't happen. And so if we'll have exactly three lines, we will have a triangular piece indeed. What happens when we add one more line? So now we have just three lines and we are adding one more, so it will be the fourth line. And as we have three lines, we have this highlighted triangle. Now with for example such fourth line. And we see that it intersects the triangle. But let's see how does it intersect the triangle. So it goes somewhere from the left. And then it goes and goes and then at some point it intersects one of the sides of the triangle. And then it is going inside of the highlighted triangle. And it goes and goes and then it intersects the triangle again, and goes out of the triangle. And then it goes to the right to infinity, and this is what always happens. Line goes until it intersects some side of the triangle. And note that it cannot intersect the side exactly in the vertex, because that would be a vertex where three lines intersect, the two sides of the triangle and the new line. So that can happen. So the new line always intersects some side of triangle somewhere in the middle and then it goes inside the triangle. And we know that in the end when it goes to the right at some point it will be outside of the triangle. So it has to intersect a triangle twice, not just once but twice. So if a line intersects a triangle, it intersects it in two points and it intersects two of the sides. So if we take these two points and the vertex where these two sides intersect themselves, those form a triangle. And this is actually the new triangle that will appear when we add a new line that intersects the current triangle. So, every time we add a new line that intersects the current triangle, a new triangle is formed. What happens if we add another line, the fifth line? In this case, this fifth line doesn't touch the existing triangle which exists after four lines. So when it doesn't touch, we can just say that this same triangular piece remains intact? And so when we're going from four lines to five lines, the same triangle exists. Now, let's consider the general case. In the general case there can be many, many lines. And of course sometimes we can spot the triangle with a naked eye. But if we had many, many more lines, like thousands of them, it will be very hard to find a triangle by our naked eye. And we need to somehow prove for ourselves that for any possible positions of those lines which satisfy requirements, there will be actually a triangle. So in general, we are going to do the following. We assume that we have already added some number of lines, maybe 3, maybe 4, maybe 100. And up to this point, some triangle piece existed. And we're going to add new lines one by one. And we can get actually any picture with many lines. We can get by adding them one by one in some order. And the order doesn't matter to us. So we just select some order, we add first three lines, and then we add one more line at each step. So we assume that at some point when we were at, for example, 100 lines, there was some triangle. And here is this triangle highlighted with orange. And we are focusing exactly on that triangle. We forget about everything to the side from this triangle. Only know that no lines intersect this triangle because this is a whole piece. And we know that there are a lot of lines going here and there on the plane. But we don't need them to make our proof. So there is a triangle, and now we're going to add one more line. And if that line intersects this triangle, then we already know that it will intersect two sides of the triangle and a new triangle will be formed like this. So this happens not only when we have three lines, it happens whenever we already have a triangle and it may with 3 lines or 100 lines or 1 million lines. That doesn't matter. Still, if the new line intersects our current triangle, a new triangle appears. Otherwise, if we have a triangle and the new line doesn't touch it, then this triangle just remains. So in the general case it happens the same way as in the case of just three lines. [MUSIC]
