3
$\begingroup$

This question already has an answer here:

Suppose that $n$ lines are drawn on a plane in such a way that no lines are parallel and no three of them intersect at a point. Let $r(n)$ be the number of regions the plane is divided into after drawing the $n$ lines. Find a recursive formula and prove it without induction.

Progress

I found that the formula $r(n)=r(n-1) + n$ works but am having trouble proving it.

$\endgroup$

marked as duplicate by Joel Reyes Noche, user147263, Rebecca J. Stones, Surb, Najib Idrissi Mar 12 '15 at 9:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ can you do induction ? $\endgroup$ – DeepSea Feb 13 '15 at 1:26
  • 4
    $\begingroup$ This is worked in Concrete Mathematics by Graham, Knuth, and Patashnik. In any event, please use a better title and be more specific in your tagging. $\endgroup$ – apnorton Feb 13 '15 at 1:27
  • 2
    $\begingroup$ Remove one line; how many pairs of regions get merged? $\endgroup$ – user147263 Feb 13 '15 at 2:02
5
$\begingroup$

Suppose that you have $n$ lines and $r(n)$ regions, and you add a line that is not parallel to any of the current $n$ and does not pass through any point where two of them intersect. The new line must intersect each of the $n$ original lines in a single point; why? Suppose that it intersects them in the points $p_1,\ldots,p_n$, in that order. These $n$ points divide the new line into $n+1$ sections: the $n-1$ bounded sections $\overline{p_1p_2},\overline{p_2p_3},\ldots,\overline{p_{n-1}p_n}$, and the unbounded rays ‘before’ $p_1$ and ‘after’ $p_n$. Each of these sections divides a region into two regions, so each of them adds one region to the total. Therefore $r(n+1)=r(n)+\ldots\;$?

$\endgroup$

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