# Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions…Induction!

Show that $n$ lines separate the plane into $\frac{(n^2+n+2)}{2}$ regions if no two of these lines are parallel and no three pass through a common point.

I know we start with the base case, where, if we call the above equation P(n), P(0), for 0 lines would be 0. But I really have no idea how to begin the inductive step. How do we know what k+1 we're supposed to arrive at?

Thanks!

-
looks like $\binom{n-1}{2} + 1$ –  Santosh Linkha Oct 9 '12 at 5:50

With $0$ lines, there is $1$ region and no intersections of lines.
Each time a line is added and it crosses $k$ other lines it adds $k+1$ regions and $k$ intersections. Another way of looking at this is that for each line and $k$ intersections added, $k+1$ regions are added (the number of added lines and intersections).
Therefore, the number of regions is $1+\text{the number of lines}+\text{the number of intersections}$. With $n$ lines, there are $\binom{n}{2}$ intersections (if no two lines are parallel and no three lines are coincident).
Thus, the number of regions is $\binom{n}{2}+n+1=\frac{n(n-1)}{2}+n+1=\frac{n^2+n+2}{2}$.
@Bob: Note that robjohn’s answer essentially gives you your induction step: when you add the $(n+1)$-st line, it cuts $n+1$ regions in two, so it adds $n+1$ regions. Add that to the $\frac12(n^2+n+2)$ given you by your induction hypothesis, and you get $\frac12(n^2+3n+4)=\frac12\left((n+1)^2+(n+1)+2\right)$. –  Brian M. Scott Oct 9 '12 at 7:24