Number of Regions N Lines Divide Plane

Below I give two solutions to a well-known problem. One standard, the other - in my view - beautiful.

What is the maximum number $L_n$ of regions defined by $n$ lines in the plane?

Solution 1

We find and then solve a recursive formula for $L_n,$ see [Concrete Mathematics, 4-8].

Obviously $L_0=1$ and $L_1=2.$ Short experimentation will convince you that $L_2=4.$ However, the next number that intuition often suggests, i.e., $L_3=8$ does not hold. Instead, $L_3=7.$ Why so? This is because, if we want to obtain the maximum possible number of regions, we shall not let the new line pass through the intersection of the first two, for then we would get six regions and can do better. Leaving that point on one side of the third line means that the line won't be able to cross all four already existent regions, but at most only three - one more than there are lines. This gives a clue to a general case.

References

1. A. Engel, Problem-Solving Strategies, Springer Verlag, 1998
2. R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994