How many regions do N lines divide a plane?
Explanations: N straight lines are drawn on a plane paper. Each line intersects with rest all lines. That means N’th line intersects N-1 lines. You can assume infinite number of lines can be drawn on that paper. You have to find total regions after N lines are drawn. An image is given below to understand the problem clearly. Solve Approach: From above picture we see that base case L[0] = 1 (here, L = Lines). Whenever a line is drawn it intersects all other lines. Lets try to find the pattern from the picture. L[1] = 2, When 1st line is drawn it intersects 0 line. So, L[1] = 1+L[0] = 1. When 2’th line is drawn it intersects 1 lines. So, L[2] = 2+L[1] . Because when intersecting 1 line it creates 2 new regions. You can see for yourself by drawing on text paper. Again, when 3rd line is drawn it intersects 2 lines and creates 3 new regions. Thus, L[3] = 3+L[2]. From observation we see that, when N’th line is drawn and it intersects N-1 lines and creates N new regions. The total regions become new regions + old regions. So, for N lines, L[n] = N+L[n-1]. To know answer of L[n] we need to know L[n-1], To know L[n-1] we need to know L[n-2]….and in ending stage L[0]. Thus, we can say that recurrent solution exists for this problem. ...