[SOUND] Now we're ready to prove with the induction the following theorem. For any n greater or equal to 3 and any n straight lines on a plane, if every two of them intersect, and all the intersection points are different, then there is a triangular piece among the pieces into which these lines cut the plane. So let's see the structure of the proof. First, we prove that for any three lines that satisfy our requirements, there will be a triangle. Then, we can make a step from three lines to four lines. We note, that to get any four lines from the plane, we can actually first get some three of them on the plane. And then adds the fourth on top of it. And we assume that for any three lines on the plane, there will be a triangle. Given that, we prove that for any four lines there will be triangle. To do that, we remember that when we add a new line, either a new triangle appears or the same triangle stays. So we can prove that if, for n equals 3 our statement is true, then it is true for n equals 4. And we already know, because we've proved it separately, that for n equals 3 the statement is true. So now we can make the step from 3 to 4, and we know that for any four lines there will be a triangle. Now we want to make the next step and prove that for any five lines, there will be a triangle. To do that, we prove a step from 4 to 5 that if we assume that for any four lines there is a triangle, then we can prove that for any five lines there will be a triangle also. To do that, we say that any five lines you can get by first selecting some four of them, drawing them, and then adding the fifth one on top. By the assumption of our induction for those four lines, there will be some triangular piece. And when we add the fifth line on top, either the same triangle remains or a new triangle appears. So for those five lines there will also be a triangle. And so, we know that if for four n equals 4, our statement is true, then it is also true for n equals 5. And we actually already know that for n equals 4 the statement is true, so now we know that it is also true for n equals 5. And we can make the same step from 5 to 6, but what we want to do is to make all the steps at the same time. One to go from 6 to n for any integer n, which is greater or equal than 3. To do that, instead of doing one step at a time, which would take for us infinite time, we prove a more general thing. That if for some k, we have proven that any for any k lines on the plane there is a triangle. Then for any k + 1 lines there will also be a triangle. And to do that, we'll say that to get any k + 1 lines, we can first select some k of them, draw them on a plane, and then add the k plus first one on top of it. We know that for those k lines there will be a triangle, and we know that when we add the k plus first line, either this triangle remains or a new triangle appears. So if for k, the statement's true, then it is also true for k + 1. And as soon as we have proven that in the general case from k to k + 1, we can actually make the step from 6 to n. And actually, we didn't need to prove the intermediate steps from 3 to 4, from 4 to 5, from 5 to 6. We could just go directly from 3 to n, as soon as we have proven this general case from k to k + 1. And this is how mathematical induction works. So our proof as a whole consists of the following parts, first we'll prove what is called induction base. This is the basic statement for some smallest value of n for which we need our statement. In this case n equals 3 and three lines. We prove that there will be a triangle for three lines. Then, we prove that if our statement true for n equals 3, then it is true for n equals 4. After that we prove that if it is true for n equals 4, then it's also true for n equals 5, and so on. And then we prove the more general thing which is called induction step from n to n + 1. We proved that in the general case, if for any n lines there is a triangle, then for any n + 1 lines, there is a triangle. And then after we've proven both the induction base and induction step, we actually have the profit we needed. We have proven the whole theorem, the whole statement, and actually we can shorten this path a little bit. And what we'll get is that, we actually need to do only two things, prove the induction base in this case n equals 3, and prove the induction step from n to n + 1 in the general case. We don't need these intermediate steps from three to four, from four to five, and so on. Just prove the general induction step. And if we have proven those two things, then we have proven our theorem. And we will see more examples of that in the next videos. [SOUND] [MUSIC]