# $n$ Lines in the Plane

How am I to "[u]se induction to show that $n$ straight lines in the plane divide the plane into $\frac{n^2+n+2}{2}$ regions"? It is assumed here that no two lines are parallel and that no three lines have a common point. Further, this is not a non-Euclidean problem, but I wouldn't mind a discussion on the non-Euclidean nature of the problem.

I was thinking it might be easier to show using the unit sphere.

A GOOD REFERENCE I FOUND THAT WILL BE USEFUL TO ANYONE COMING ACROSS THIS PROBLEM IS Concrete Mathematics, Graham, Knuth, Patashnik pp. 4–8.

• Could you elaborate on what you mean by "the non-Euclidean nature of the problem", and what you're hoping to get? I wasn't sure what to say because I didn't understand what you were asking. – MJD Jul 8 '13 at 18:46
• Well, say whatever you'd like. I mean two lines being parallel probably needs to be adjusted. Would this work in that case? – Trancot Jul 8 '13 at 18:54
• If you're in a space where there are no parallel lines, you can disregard that condition. If you're in a hyperbolic space where there are multiple parallels, it doesn't change. – MJD Jul 8 '13 at 19:18
• Is this not a duplicate of this question? – robjohn Sep 27 '13 at 19:36
• @MJD Why did you edit it that way? You've just robbed the lazy mathematician of information. Do you really think that people are going to look that reference up? Having it up like I had earlier gives people access to a good source of knowledge, which they themselves might not be able to find on their own. I'm thinking freshman undergraduates, and other people without the background knowledge necessary to just go an get it through the library. I think it ought to be as it was. – Trancot Sep 27 '13 at 21:11

## 1 Answer

To prove it by induction, you first prove the base case: 0 lines divide the plane into 1 region.

Then you suppose that $n$ lines divide the plane into $\frac12(n^2+n+2)$ regions, and show that $n+1$ lines divide the plane into $\frac12((n+1)^2+(n+1)+2)$ regions. Since $\frac12((n+1)^2+(n+1)+2) - \frac12(n^2+n+2) = n+1$, you need to show that adding the $n+1$'th line adds exactly $n+1$ regions, or equivalently that the $n+1$th line can be made to pass through $n+1$ of the existing regions, dividing each one into two regions.

Does that help?

• A bit. I'll work on it. – Trancot Jul 8 '13 at 18:56
• How do you "show" this last condition? – Trancot Jul 8 '13 at 19:00
• Hint: How many lines does the new line intersect? – Hagen von Eitzen Jul 8 '13 at 19:07
• @MJD See my most recent edit. – Trancot Sep 27 '13 at 15:34
• It is. I can prove it in two ways. First, in countries that are party to the Berne Convention, any original work of authorship is copyright as soon as it is fixed in a tangible medium of expression. And second, because on page iv, as you know, or should have known, it says “Copyright © 1989 by Addison-Wesley Publishing Company” and then follows with a paragraph that reads “All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted, in any form or by any means, [etc.], without the prior written permission of the publisher.” So cut it out. – MJD Sep 28 '13 at 1:52