Number of Regions in Plane Defined by Given Number of Lines

Theorem

The maximum number $L_n$ of regions in the plane that can be defined by $n$ straight lines in the plane is:

$L_n = \dfrac {n \left({n+1}\right)} 2 + 1$

Proof

Setting up a Recurrence Rule

First we consider the plane with no lines at all. This has one region, so $L_0 = 1$.

Now when we have one line, we divide the plane into two regions, so $L_1 = 2$.

Now consider the $n$th line.

This increase the number of regions by $k$ iff it splits $k$ of the old regions.

It can split $k$ of the old regions iff it hits the existing lines on the plane in $k-1$ places.

Two straight lines can intersect in at most one point.

So the new line can intersect the $n-1$ old ones in at most $n-1$ different points.

Therefore $k \le n$.

So we see that $L_n \le L_{n-1} + n$.

Now, it is always possible to place the $n$th line so that:

• It is not parallel to any of the others, and therefore intersects all the other $n-1$ lines;
• It does not go through any of the existing intersection points (so intersects them all in different places).

Thus we see that $L_n \ge L_{n-1} + n$.

Hence the recurrence:

$L_n = L_{n-1} + n$

Solution of Recurrence

Using induction, we show that $L_n = \dfrac {n \left({n+1}\right)} 2 + 1$.

The base case is straightforward:

• $L_0 = 1 = \dfrac {0 \left({0+1}\right)} 2 + 1$
• $L_1 = 2 = \dfrac {1 \left({1+1}\right)} 2 + 1$

Now assume the induction hypothesis:

$L_k = \dfrac {k \left({k+1}\right)} 2 + 1$

and try to show:

$L_{k+1} = \dfrac {\left({k+1}\right) \left({k+2}\right)} 2 + 1$

Hence the induction step:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle L_{k+1}\)	\(=\)	\(\displaystyle L_{k} + k+1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {k \left({k+1}\right)} {2} + 1 + k + 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac {\left({k+1}\right) \left({k+2}\right)} {2} + 1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	after algebra

Hence the result by induction.

$\blacksquare$

History

This was published in 1826:  Jakob Steiner: Einige Gesetze über die Theilungder Ebene und des Raumes (J. Reine Angew. Math. Vol. 1: 349 – 364).

Sources

• Ronald L. Graham,  Donald E. Knuth and Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science (1994) (2nd edition) $\S 1.2$.