Assume that there are $n$ infinitely long straight lines lying on a plane
in such a way that no two lines are parallel, and no three lines intersect
at a single point. Prove that these lines divide the plane into $\frac{n^2+n+2}{2}$ regions. (Hint: Any two non-parallel straight lines on a plane must
intersect at exactly one point.)
Can someone tell me where to start here? I know to prove the base where $n=0$, but don't know how to proceed.
Any help is greatly appreciated!
Best Answer
Suppose it is true for $n$. Now add a new line, the number of vertices increases by $n$ one with each of the old line) and the number of line segments increases by $2n+1$ (each of the $n$ old lines is broken into one more piece, and the new line has $n+1$ segments), hence by Euler's theorem on planar graphs the number of regions ($F$) increases by $n+1$ (Since $V-E+F$ is constant and $V-E$ is reduced by $n+1$).
So we now have $\frac{n^2+n+2}{2}+n+1=\frac{(n+1)^2+n+1+2}{2}$ vertices as desired.