Discrete Mathematics: Elementary and Beyond

11.2 Counting regions 183

We are not done yet; what does this give for the number of regions? We
start with 1 region for 0 lines, and then add to it 1, 2 , 3 ,...,n. This way
we get

1+(1+2+3+···+n)=1+

n(n+1)

2

(in the last step we used the “young Gauss’ problem from Chapter 1). Thus
we have proved:

Theorem 11.2.1A set ofnlines in general position in the plane divides
the plane into1+n(n+1)/ 2 regions.

11.2.1Describe a proof of Theorem 11.2.1 using induction on the number of
lines.

Let us give another proof of Theorem 11.2.1.

Proof. This time, we will not use induction, but rather try to relate the
number of regions to other combinatorial problems. One gets a hint from
writing the number in the form 1 +n+

(n

2

)

.




FIGURE 11.6.

Assume that the lines are drawn on a vertical blackboard (Figure 11.6),
which is large enough so that all the intersection points appear on it. We
also assume that no line is perfectly horizontal (it it is, we tilt the picture
a little), and that the blackboard is very long, so that every line intersects
the bottom edge of the blackboard. We may also assume that the lower