First, since a line cuts another in at most one point, a new line can cut n-1 lines in at most n-1 points. But it can cut in fewer- if it passes through an intersection of two lines. For example, suppose you have two line crossing at point P. Notice that they divide the plane into 4 areas Any new line either passes through P or it doesn't. If it does not pass through P, it crosses each of the two lines once, so cuts the two lines in two points. Three of the original 4 areas are cut into 2 while the new line does not cross the fourth (the one on the "other side" of P) so these 3 lines divide the plane into [/tex]2(3)+ 1= 7= 2^2-1[/tex] areas. But if the new line happens to go through P, the intersection of the first two lines, it crosses in only one point and only passes through 2 of the original 4 areas. Those three lines, all crossing at P, divide the plane into 2(2)+ 2= 6 areas.
k is the number of new regions created by this new line. As seen, the new line can cross n-1 lines in at most n-1 points which means it passes through n areas (it passes through a new area after each line crossing and it was in one area before the first line crossing). It divides each of those areas in two so it has created at most n new areas: .
If n lines creates at most areas, then n-1 lines create at most areas. Adding a single new line creates at most
n new areas so .