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 areaaftereach 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 .