Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
looks like $\binom{n-1}{2} + 1$ – Santosh Linkha Oct 9 '12 at 5:50

Here is the way I usually think about this (it sort of uses induction).

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}$.

share|cite|improve this answer
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.