13
$\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!

  • 0
    looks like $\binom{n-1}{2} + 1$2012-10-09
  • 0
    See also: http://math.stackexchange.com/questions/339750/greatest-number-of-planes-we-can-get-when-dividing-with-lines-and-circles2016-10-03

2 Answers 2

15

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

  • 1
    @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)$.2012-10-09
2

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 two parts and adding 4 new regions. In general the nth 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
 ......................
 ........................
   u(4) - u(3)   =  4
   u(3) - u(2)   =  3 
   u(2) - u(1)   =  2
 -------------------------- 
   u(n) - u(1)   =  2 + 3 + 4 + ..... + (n-1) + n

which we find by summing the equations.

All other terms on the left cancel between rows. We are left with:

 u(n) = u(1) + 2 + 3 + 4 + ....+ n   and   u(1) = 2

Thus:

 u(n) = 1 + [1+2+3+4+...+n]

      = 1 + n(n+1)/2

      = (2 + n^2 + n)/2

So:

 u(n) = (n^2+n+2)/2

If you allow parallel lines and more than 2 lines to intersect at a point, the answer becomes undefined.