Into how many finite regions does $n$ lines in general position divide the plane?

I have $$n$$ lines in the plane such that no two are parallel and no three lines intersect in a common point.

Into how many finite regions do the lines divide the plane?

I came up with this recurrence relation: $$x_3=1, \qquad x_n=x_{n-1}+n-2 ,$$ and I found out it is correct. Even though I solved it intuitively, I'd like to understand how to prove this recurrence relation formally. How can I do it?

• here is a good write up. If you search online, you'll find others. – lulu Aug 15 at 16:55
• But why do you think $X_3=1$? Three lines in general position create $7$ regions – lulu Aug 15 at 16:57
• @lulu Maybe OP wants only bounded regions. – Don Thousand Aug 15 at 16:58
• @MatthewDaly and @ lulu, you seem to have missed the word "finite" in "how many finite regions." As such, both proposed links, although useful for techniques, answer the related but different question of counting how many regions are possible where we don't care if the regions are finite. – JMoravitz Aug 15 at 16:58
• @JMoravitz Ah, thank you. – lulu Aug 15 at 16:58

The number of intersections---and hence the number of regions bounded below---is at most $${n \choose 2} = \frac{1}{2} n (n - 1)$$, and this number is achieved exactly when the lines are in general position (i.e., no two lines are parallel, and no three lines intersect in a point). If we draw a horizontal line above all of the intersections (like the dotted line in the diagram), it intersects all $$n$$ of the lines in the original configuration (again, since none of those lines are horizontal), and so there are $$n - 1$$ regions corresponding to a vertex and unbounded above. (In the diagram, these are the regions marked by red angles.) Since every unbounded region is unbounded above or unbounded below, the maximum number of bounded regions is $$\frac{1}{2} n (n - 1) - (n - 1) = \color{#df0000}{\boxed{\frac{1}{2} (n - 1) (n - 2) = {n - 1 \choose 2}}} .$$ A standard induction argument shows this quantity value coincides with the term $$x_n$$ of your sequence for every $$n$$.
(Alternatively, if you take as given the result that $$n$$ lines in general position divide the plane into $${n + 1}\choose 2$$ regions (including unbounded regions), then since $$n$$ lines yield $$2 n$$ unbounded regions---to see this, draw a circle enclosing all of the intersections of the lines---there are $${{n + 1}\choose 2} - 2 n$$ bounded regions.)