How to Prove the Recurrence Relation for the Number of Regions in a Plane?

[e(ho0n3]

Hi everyone,

I'm stumped on this problem: Let R_n denote the nubmer of regions into which the plane is divided by n lines. Assume that each pair of lines meets in a point, but that no three lines meet in a point. Derive a recurrence relation for the sequence R_1, R_2, ...

After doing a couple of examples, the recurrence relation seems to be

R_n = R_{n-1} + n​

. I want to prove that this is the proper recurrence relation. More specifically, I want to show that when I cut a plane consisting of R_k regions with the appropriate line, k+1 of those regions will be divided in two so that the number of regions is R_{k+1} = R_k + k + 1. I can't think of any geometrical argument for this. Any tips?

 

[AKG]

Okay, well you know there are k existing lines. Now, the (k+1)th line can, at maximum, cut through the k lines (if it is parallel to anyone line, it will not cut it). Show that this is possible, and that it is optimal. Also, recognize that if it passes through n lines, it cuts n+1 regions in half. Basically, you can think of the existing lines forming boundaries of regions, and include some boundaries at infinity. If the line goes from one boundary at infinity to another at infinity, and cuts through n lines, then the points it intersects (imagine it intersects some points at the infinite boundary) form a set. You'll notice that every consecutive pair of points it intersects means that it cuts a region in half. If there are n points in the set (including the 2 at infinity) then there will be n-1 split regions. Of course, since there are k lines, and we're including 2 boundary points, n-1 = k+1, so it splits k+1 regions. This is of course a rough argument, you can fix it up so that you're not treating it as though there are lines at infinity, but the idea is right.

 

[Gokul43201]

Or you can use the Euler relation for the plane (F(n)+V(n)-E(n)=1), along with AKG's observations, (but you don't have to worry about regions anymore) i.e:

1. the (n+1)th line intersects the previous n lines creating n new vertices. Or, V(n+1)=V(n)+n

2. These intersections give rise to n new edges on the existing n lines and n+1 edges on the (n+1)th line.
Or E(n+1)=E(n)+n+1+n=E(n)+2n+1

Now plug these into Euler to get
F(n+1)=1-V(n+1)+E(n+1)=[1-V(n)+E(n)]+2n+1-n=F(n)+n+1

which is what you want.

 

[e(ho0n3]

My lack of intuition disables me from understanding your argument very well.

Okay, well you know there are k existing lines. Now, the (k+1)th line can, at maximum, cut through the k lines (if it is parallel to anyone line, it will not cut it). Show that this is possible, and that it is optimal.

What do you mean 'optimal'? What makes it optimal? The only way I can think of showing this is using one of Euclid's axioms.

Also, recognize that if it passes through n lines, it cuts n+1 regions in half. Basically, you can think of the existing lines forming boundaries of regions, and include some boundaries at infinity. If the line goes from one boundary at infinity to another at infinity, and cuts through n lines, then the points it intersects (imagine it intersects some points at the infinite boundary) form a set. You'll notice that every consecutive pair of points it intersects means that it cuts a region in half. If there are n points in the set (including the 2 at infinity) then there will be n-1 split regions. Of course, since there are k lines, and we're including 2 boundary points, n-1 = k+1, so it splits k+1 regions. This is of course a rough argument, you can fix it up so that you're not treating it as though there are lines at infinity, but the idea is right.

Interesting argument. Maybe things would be simpler if I just assume the plane is finite. I'll think about this some more and I'll post a proper argument when I have something.

Or you can use the Euler relation for the plane (F(n)+V(n)-E...

I would like to solve this problem without using graph theory (since this problem came from the chapter right before the chapters on graph theory). I'll consider this solution later on. Thanks.

 

[Gokul43201]

Okay, well you know there are k existing lines. Now, the (k+1)th line can, at maximum, cut through the k lines (if it is parallel to anyone line, it will not cut it). Show that this is possible, and that it is optimal.

This is simply an extension of the Euclidean axiom that says "2 lines intersect at most, at one point". I don't believe there is any need to optimize anything in it.

 

[AKG]

What do you mean 'optimal'? What makes it optimal? The only way I can think of showing this is using one of Euclid's axioms.

I suppose it's a trivial point, but show that it is, for example, better than having 2 parallel lines in there somewhere, or having a line pass through an existing point of intersection. I had a nice big thing on proving this with diagrams and everything, including an extension to 3-space, as well as the recurrence relation derived for 3-space, but I think I only have it in hard copy now. meh...

Interesting argument. Maybe things would be simpler if I just assume the plane is finite. I'll think about this some more and I'll post a proper argument when I have something.

You can treat the plane (two-space) as an infinitely large square, or circle, whatever works best. The assignment I was talking about in the paragraph above asked about slicing a pizza and a loaf of bread, and we did this with some analogies, treating 2-space as a very big pizza...