## Going Around in Circles

If we pick any two distinct points on a circle, and connect them with a chord, the chord will divide the interior of the circle into two distinct, nonintersecting regions. If we pick three distinct points on a circle and connect each pair of them with a chord, we can form four distinct, nonintersecting regions. What is the maximum number of nonintersecting regions that we can form by selecting four distinct points on a circle and connecting each pair of them with a chord? By selecting five distinct points? Six distinct points? And of course, then, $n$ distinct points?
Source: NCTM Problem to Ponder 11/2011

SOLUTION

One point: $0$ chord, $0$ intersection, $1$ region

Two points: $1$ chord, $0$ intersection, $2$ regions

Three points: $3$ chords, $0$ intersection, $4$ regions

Four points: $6$ chords, $1$ intersection, $8$ regions

Five points: $10$ chords, $5$ intersections, $16$ regions

Six points: $15$ chords, $15$ intersections, $31$ regions

Seven points: $21$ chords, $35$ intersections, $57$ regions

We tabulate the previous data in the following table

Looking at the table, we easily notice a pattern:
$Regions=Chords+Intersections+1$
But, is it true for all values of $n$?
When we add a new point, the number of chords, intersections, and regions increase. But by how much? We will now examine in depth the transition from a 5-point circle to a 6-point circle in order to gain insights into the increase of these numbers.
Let $R$ denote the number of regions; $C$ the number of chords; $I$ the number of intersections. We start from a 5-point circle as shown in the figure below

$C=10,\; I=5,\; R=16$
Now, let’s add a sixth point and draw chord $A$.
Chord $A$ does not intersect any old chord and splits an old region into two. The number of regions $R$ increases by $1$ from $16$ to $17$.

Chord $B$ intersects $3$ old chords and splits $4$ old regions into $8$. $R$ increases by $4$ from $17$ to $21$.

Chord $C$ intersects $4$ old chords and splits $5$ old regions into $10$. $R$ increases by $5$ from $21$ to $26$.

Chord $D$ intersects $3$ old chords and splits $4$ old regions into $8$. $R$ increases by $4$ from $26$ to $30$.

Chord $E$ does not intersect any old chord and splits an old region into two. $R$ increases by $1$ from $30$ to $31$.

Summary
When we add a point, we add several new chords. A new chord may intersect no old chord or may intersect several old chords at several intersection points. When a new chord intersects an old chord it leaves an old region and enters another old region splitting each old region it passes through into two. Hence, it follows that the increase in $R$ will be one more than the increase in $I$ including the case where the new chord does not intersect any chord. In other words,
$\Delta R=\Delta I+1$

Proof by induction
Show that $R=C+I+1$ for all positive integers $n=1,2,3,\cdots$
$n=1$
$1=0+0+1$
The formula is true for $n=1$

Suppose it is true for $n$. We write
$R_n=C_n+I_n+1$
We want to show that it is true for $n+1$, that is
$R_{n+1}=C_{n+1}+I_{n+1}+1$
When we add a point, we add a number of new chords. If the new chord does not intersect any old chord,
$\Delta I=0$
$\Delta C=1$
$\Delta R=\Delta I+1$
$=0+1$
$=1$
$R_{n+1}=R_n+\Delta R$
$=R_n+1$
$C_{n+1}+I_{n+1}+1=\left (C_n+\Delta C\right )+\left (I_n+\Delta I\right )+1$
$=\left (C_n+1\right )+\left (I_n+0\right )+1$
$=\left (C_n+I_n+1\right )+1$
$=R_n+1$
Comparing the equations we conclude that
$R_{n+1}=C_{n+1}+I_{n+1}+1$

If the new chord intersects $k$ old chords at $k$ intersection points
$\Delta I=k$
$\Delta C=1$
$\Delta R=\Delta I+1$
$=k+1$
$R_{n+1}=R_n+\Delta R$
$=R_n+k+1$
$C_{n+1}+I_{n+1}+1=\left (C_n+\Delta C\right )+\left (I_n+\Delta I\right )+1$
$=\left (C_n+1\right )+\left (I_n+k\right )+1$
$=\left (C_n+I_n+1\right )+k+1$
$=R_n+k+1$
Comparing the equations we conclude that
$R_{n+1}=C_{n+1}+I_{n+1}+1$
DONE

Now that we have proved the formula $R=C+I+1$, it is time to express it in terms of $n$.
A chord connects two points. How many ways can we select two points from a collection of $n$ points?
$C=\binom {n}{2}$
Two chords (connecting four points) intersect at one point. How many ways can we select four points from a collection of $n$ points?
$I=\binom{n}{4}$
The formula expressed in terms of the number of points $n$ is
$R=\binom{n}{2}+\binom{n}{4}+1$

Verification
$R_1=\binom{1}{2}+\binom{1}{4}+1$
$=0+0+1$
$=1$

$R_2=\binom{2}{2}+\binom{2}{4}+1$
$=1+0+1$
$=2$

$R_3=\binom{3}{2}+\binom{3}{4}+1$
$=3+0+1$
$=4$

$R_4=\binom{4}{2}+\binom{4}{4}+1$
$=6+1+1$
$=8$

$R_5=\binom{5}{2}+\binom{5}{4}+1$
$=10+5+1$
$=16$

$R_6=\binom{6}{2}+\binom{6}{4}+1$
$=15+15+1$
$=31$

$R_7=\binom{7}{2}+\binom{7}{4}+1$
$=21+35+1$
$=57$

$R_8=\binom{8}{2}+\binom{8}{4}+1$
$=28+70+1$
$=99$

Answer: $R=\binom{n}{2}+\binom{n}{4}+1$.