1

So I have been working on these proofs for a while and finished 13 of 14 of them but I was never able to figure this one out so I thought I would ask for help on how it would be done:S

Here is the question:

Let $n\ge$ be an integer. Consider $2n$ straight lines $L_1,L_1',L_2,L_2',\ldots,L_n,L_n'$ such that:

  • For each $i$ with $1 \le i \le n$, $L_i$ and $L_i'$ are parallel.
  • No two of these lines $L_1,\ldots,L_n$ are parellel,
  • No two of these lines $L_1',\ldots,L_n'$ are parallel
  • No three of the $2n$ 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 the regions by $R_n$.

Derive a recureence from the number $R_n$ and use it to prove that $R_n = 2n^2 + 1$ for $n\ge1$

I don't understand how I should be going about this problem, I think the question is unclear (atleast in my mind, hopefully someone can give me the general direction I could be going with this though). Any help at all would be tons of help. Thanks!

bof
  • 78,265
user144808
  • 143
  • Where you wrote "There lines", did you mean "Three lines"? – Michael Hardy Oct 15 '14 at 16:26
  • To go from $n$ to $n+1$, you add two parallel lines that only intersect one other line at a time. Imagine a place filled with those lines and a line being draw from farm away towards where it can intersect other lines. Each time it will intersect a line, it'll "finish" splitting a region in two. If you can see what I'm talking about, you should be able to figure out the formula. If not, try an example. – xavierm02 Oct 15 '14 at 16:27
  • @MichaelHardy Ya It was ment to be "these lines" Sorry for the typo – user144808 Oct 15 '14 at 16:30

3 Answers3

2

Say you have $r_n$ regions when there are $2n$ lines. Now you add $L_{n+1}$; it’s not parallel to any of $L_1,\ldots,L_n$ or $L_1',\ldots,L_n'$, so it eventually crosses every one of those $2n$ lines. That means that it runs through $2n+1$ of the regions formed by the first $2n$ lines. (Why?) Whenever it runs through a region, it splits that region in two. By how much does this increase the number of regions? Now add $L_{n+1}'$ parallel to $L_{n+1}$. How many regions does it cut in two? By how much does that increase the number of regions?

Once you have all that, you can express $r_{n+1}$ in terms of $r_n$ and $n$ to get your recurrence.

Brian M. Scott
  • 616,228
  • I sort of realized that but didn't really know how to express it. Its like, I understand it, just can't prove it:D – user144808 Oct 15 '14 at 16:54
  • @user144808: Can you answer any of the specific questions? – Brian M. Scott Oct 15 '14 at 16:59
  • You mean related to this one? Or the other ones I had, if you mean the other ones I had, yes I have answered them all, this was the only one I couldn't do. – user144808 Oct 15 '14 at 17:01
  • @user144808: I mean the questions in my hint. – Brian M. Scott Oct 15 '14 at 17:03
  • sure, every time it splits it in two it increases number of reasons by 1. For the L'n is cuts n regions into 2n regions (I think). And that also increases the number of regions by n total? Though that seems like it might be wrong – user144808 Oct 15 '14 at 17:38
  • @user144808: $L_{n+1}$ crosses all $2n$ of the earlier lines. That means that it crosses more than $n$ regions; how many? (If you don’t see it right away, try drawing some examples with small $n$.) – Brian M. Scott Oct 15 '14 at 17:40
  • It makes 2n+1 new regions? right? But doesn't L'n+1 also make 2n+1 new regions? – user144808 Oct 15 '14 at 18:17
  • @user144808: Yes to both, so you get altogether $4n+2$ new regions. And therefore $r_{n+1}=\ldots;$? – Brian M. Scott Oct 15 '14 at 18:28
  • Rn+1 = Rn + 4n+2 right? But I don't see how that proves Rn = 2n^2 +1 – user144808 Oct 15 '14 at 18:45
  • 1
    @user144808: Yes, you have the right recurrence. You also know that $R_1=3$. Use the recurrence to prove by induction on $n$ that $R_n=2n^2+1$ for $n\ge 1$. – Brian M. Scott Oct 15 '14 at 18:49
  • ok I kinda get it for the most part, thank you for all the help. Sorry you had to like, force feed me all the smaller problems for me to be able to figure it out:S Thanks a bunch tho – user144808 Oct 15 '14 at 18:57
  • @user144808: You’re welcome! – Brian M. Scott Oct 15 '14 at 19:01
0

As you draw each line, count how many other lines you cross. Relate the number of other lines you cross to how many regions you add.

dshin
  • 1,525
0

This is a nonrecursive way using the Euler formula $V-E+F=1$ where $V,E,F$ are the numbers of vertices, edges, and faces of the final graph. We first need to find $V,$ the number of vertices. Each of the $2n$ lines intersects all but its parallel companion line, so it meets $2n-2$ other lines. The expression $2n(2n-2)$ would "double count" the vertices, since each vertex is on two of the lines, so we have $V=n(2n-2).$

We also need $E,$ the number of edges. Each line has $2n-2$ vertices on it, so these divide that line into $2n-1$ edges of the graph. So we have $E=2n(2n-1).$

Finally, solving the Euler equation for $F$ gives the result $$F=E+1-V=2n(2n-1)+1-n(2n-2)=2n^2+1$$ for the number of faces or "regions".

Note: I know the OP specifically requested a recurrence, but only include this as an alternate way to look at the problem.

coffeemath
  • 29,884
  • 2
  • 31
  • 52