1

Let m≥1 and n≥1 be integers. Consider m horizontal lines and n non-horizontal lines such that no two of the non-horizontal lines are parallel, no three of the m+n lines intersect in one single point. These lines divide the plane into regions (some of which are bounded and some of which are unbounded). Denote the number of there regions by Rm,n. Derive a recurrence for the numbers Rm,n and use it to prove that $$Rm,n = 1 +m(n+1) + {n+1 \choose 2}$$

I can't understand how to approach this question. Any hints will be highly appreciated

user2847624
  • 71

1 Answers1

0

Hint: To show $R_{m+1,n} = R_{m,n} + (n + 1)$ consider what happens when you add one more horizontal line: It will intersect all of the $n$ non-horizonal lines in distinct positions, splitting all the regions it intersects into two regions. If you have $n$ non-horizontal lines then the number of segment intersections you will get that are between two non-horizontal lines or on either extreme side of the $n$ non-horizontal lines will be $n+1$. You can apply essentially the same reasoning assuming that you have $n$ non-horizontal lines and $m$ horizontal lines and you add one more non-horizontal line.

user2566092
  • 26,142