Number or regions formed when $n$ points on a circle are joined

The maximum number $R_{n}$ of regions formed when $n$ points on a circle are joined in pairs is $\frac{1}{24}\left(n^{4}-6n^{3}+23n^{2}-18n+24\right)$.

This is a fact that I have read in several essays on the dangers of jumping to conclusions in mathematics.

In your opinion, what's the quickest (and/or nicest) way to prove this formula?

Professor Paul Zeitz explains somewhere an especially convincing way to tackle this pearl following an idea which a certain high schooler in one of his talks (lectures?) came up with; yet, I don't remember where it was that I actually read this...

Let me thank you in advance for your insightful replies.

Solution 1:

Note that the number of line segments created by connecting $n$ points is $\binom{n}{2}$ (one for every pair of points) and the number of intersection points is $\binom{n}{4}$ (one for every four points). With no points, we have one region. Each time we add a line segment with $k$ intersections, we add $k+1$ regions (by splitting $n+1$ regions); think of this as one region for each line segment and one region for each intersection. Thus, the number of regions is $$ \binom{n}{4}+\binom{n}{2}+\binom{n}{0}\tag{1} $$

Since $\binom{n}{k}=0$ for $n\gt k$, we can write $$ 2^n=(1+1)^n=\sum_{k=0}^\infty\binom{n}{k}\tag{2} $$ and likewise $$ 0^n=(1-1)^n=\sum_{k=0}^\infty(-1)^k\binom{n}{k}\tag{3} $$ Adding $(2)$ and $(3)$ and dividing by $2$ yields $$ 2^{n-1}=\sum_{k=0}^\infty\binom{n}{2k}\tag{4} $$ Therefore, for $1\le n\le5$, we have $$ \binom{n}{4}+\binom{n}{2}+\binom{n}{0}=2^{n-1}\tag{5} $$ However, this pattern breaks down for $n\ge6$; this is because the $k=3$ term of $(4)$ is no longer $0$.

Thus, using the right side of $(5)$ to answer the question about dividing the interior of a circle works only up to a point. Furthermore, since the correct answer for $6$ points is $31$, students tend to recount the number of regions in their drawing several times.

Solution 2:

A quick proof of the formula works using (Euler's) polyhedron theorem.

In the picture we have $\binom{n}4$ intersections inside and $n$ along the circle; this is $V=\binom{n}4+n$ vertices.

The degree of each boundary vertex is $n+1$ ($2$ arcs and $n-1$ diagonals); each interior intersection point has degree $4$. So, the sum of degrees in the graph is $n\cdot(n+1)+\binom{n}4\cdot 4$, and therefore the number of edges is $E=\frac12\left( n\cdot(n+1)+\binom{n}4\cdot 4 \right) = \frac{n(n+1)}2 +2\binom{n}4$.

If there are $R$ regions inside the circle and one outside then the polyhedron theorem gives $(R+1) + V = E +2$, so $$ R = 1+E-V = 1 +\left(\frac{n(n+1)}2+2\binom{n}4\right) - \left(\binom{n}4+n\right) = 1+\binom{n}2+\binom{n}4. $$