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

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
• – Martin Sleziak Oct 3 '16 at 23:39

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

Suppose we draw $$n$$ straight lines on the plane so that every pair of lines intersects (but no $$3$$ lines intersect at a common point). Into how many regions do these $$n$$ lines divide the plane?

With $$n = 1$$ we divide the plane into $$2$$ regions. With $$n = 2$$ we have $$4$$ regions; with $$n = 3$$ we get $$7$$ regions. A fourth line will meet the other $$3$$ lines in $$3$$ points and so traverse $$4$$ regions, dividing them into $$2$$ parts and adding $$4$$ new regions. In general the $$n^{th}$$ line will add $$n$$ new regions:

$$u(1) = 2$$ $$u(2) = 4$$ $$u(3) = 7$$ $$u(4) = 11$$

And so on, where $$u(n) =$$ number of regions with $$n$$ lines.

We get the recurrence relationship:

$$u(n+1) = u(n) + (n+1)$$

We get the following chain of equations:

$$u(n) - u(n-1) = n$$ $$u(n-1) - u(n-2) = n-1$$ $$u(n-2) - u(n-3) = n-2$$ $$\vdots$$ $$u(4) - u(3) = 4$$ $$u(3) - u(2) = 3$$ $$u(2) - u(1) = 2$$

Adding these equations, we get: $$u(n) - u(1) = 2 + 3 + 4 + ..... + (n-1) + n$$

All other terms on the left cancel between rows, and we are left with:

$$u(n) = u(1) + 2 + 3 + 4 + \ldots + n$$

We know, $$u(1) = 2$$

Thus:

$$u(n) = 1 + (1+2+3+4+ \ldots+n)$$ $$\implies u(n) = 1 + \dfrac{n(n+1)}{2}$$ $$\implies u(n) = \dfrac{n^2 + n + 2}{2}$$

So:

$$u(n) = \dfrac{n^2 + n + 2}{2}$$

Remark $$\,$$ If you allow parallel lines and more than $$2$$ lines to intersect at a point, the above relation doesn't hold.

The answer then depends on the number of lines intersecting at a point or the number of lines which are parallel to one another.