# Induction proof: n lines in a plane

Assume that there are $n$ infinitely long straight lines lying on a plane in such a way that no two lines are parallel, and no three lines intersect at a single point. Prove that these lines divide the plane into $\frac{n^2+n+2}{2}$ regions. (Hint: Any two non-parallel straight lines on a plane must intersect at exactly one point.)

Can someone tell me where to start here? I know to prove the base where $n=0$, but don't know how to proceed. Any help is greatly appreciated!

• Consider what happens if you have already $n$ lines (and $R_n$ regions), and place a $n+1$-th line, and thus get $R_{n + 1}$ regions. – vonbrand Sep 15 '15 at 23:11
• You should probably start with $n=1$. Then consider what next line will result in, how many lines will the next line intersect? – skyking Sep 15 '15 at 23:12

Suppose it is true for $n$. Now add a new line, the number of vertices increases by $n$ one with each of the old line) and the number of line segments increases by $2n+1$ (each of the $n$ old lines is broken into one more piece, and the new line has $n+1$ segments), hence by Euler's theorem on planar graphs the number of regions ($F$) increases by $n+1$ (Since $V-E+F$ is constant and $V-E$ is reduced by $n+1$).
So we now have $\frac{n^2+n+2}{2}+n+1=\frac{(n+1)^2+n+1+2}{2}$ vertices as desired.
The statement is true for $n=1$, since $1$ line separates the plane into $2$ regions, and $(1^2+1+2)/2=2$. Assume that inductive hypothesis, that $n$ lines of the given type separate the plane into $(n^2+n+2)/2$ regions. Consider an arrangement of $n+1$ lines. Remove the last line. Then there are $(n^2+n+2)/2$ regions by the inductive hypothesis. Now we put the last line back in, drawing it slowly, and see what happens to the regions. As we come in "from infinity," the line separates one infinite region into two (one on each side of it); this separation is complete as soon as the line hits one of the first $n$ lines. Then, as we continue drawing from this first point of intersection to the second, the line again separates one region into two. We continue in this way. Every time we come to another point of intersection between the line we are drawing and the figure already present, we lop off another additional region. Furthermore, once we leave the last point of intersection and draw our line off to infinity again, we separate another region into two. Therefore, the number of additional regions we formed is equal to the number of points of intersection plus one. Now, there are $n$ points of intersection, since our line must intersect each of the other lines in a distinct point (this is where the geometric assumptions get used). Therefore, this arrangement has $n+1$ more points of intersection than the arrangement of $n$ lines, namely $(n^2+n+2)/2+(n+1)$, which, after a bit of algebra, reduces to $[(n+1)^2+(n+1)+2]/2$, exactly as desired.