14
$\begingroup$

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!

$\endgroup$
16
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ @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)$. $\endgroup$ – Brian M. Scott Oct 9 '12 at 7:24
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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