# Creative exercise with geometry and induction

Let $$S$$ be a set of $$n$$ lines such that no two are parallel and no three meet in the same point. Show by induction that the lines in $$S$$ determine $$\Theta(n^2)$$ intersection points.

I've read the definition of $$\Theta(n^2)$$, but when I draw these lines on a paper, I don't even get that it is correct that the number of intersection points is $$\Theta(n^2)$$. Because for 3 lines I get 3 intersection points, for 4 lines I get 6. And for 5 lines, it seems to be 9. So my hypothesis would rather be that it is $$3(n-2)$$ intersection points... but, of course, the book is correct, in some way...

And for $$\Theta$$-order, it is both Big-Oh and $$\Omega$$-order, so I should count $$n^2$$? Of course, for this "order functions", I may choose an $$n_0$$ that is the lower bound for $$n$$ as high as I would like, but it is impossible to visualize this on a drawing, when $$n_0$$ gets like above 5...

And, besides... counting the points using a drawing is not formal math, so how could I even know how many more intersection points adding a new line would add?

• Any two non-parallel lines intersect in exactly one points. If those points are all unique, then how many new intersections does the $n+1$st line add? You should be able to come up with a recursion here. Commented Jun 17 at 0:21
• Yes, I now understand that the n+1 th line will add n new points. So the number of points will be $\sum_{i=2}^n{i-1}$, which is $\Theta(n^2)$. Commented Jun 17 at 0:37

Let $$S(n)$$ be the number of intersections of $$n$$ non-parallel lines, where no $$3$$ lines intersect in the same point.
Clearly, $$S(1)=0$$.
Any pair of non-parallel lines intersect in exactly one point. Thus we can see that the $$n+1$$st line intersects the previous $$n$$ lines in exactly $$n$$ points. By the condition that no three lines intersect in the same point, these new points are all unique. Thus we see: $$S(n+1)=S(n)+n$$ And therefore $$S(n)=\frac{n(n-1)}{2}$$ (it is the sum of the first $$n-1$$ numbers).
One last thing which I think is important, if not required for this problem. How do we know such a set of $$n$$ lines exists? Clearly we can get them to be all non-parallel, since there are uncountably many angles to choose from. And indeed we can also get all the intersections to be unique, since we can draw our $$n$$th line sufficiently far from all the previous intersections.