The problem

Suppose you have a circle with n points lying on the perimeter of the circle and lines connecting all of the points. There would be a total of lines connecting the points (from the obvious recurrence , which was famously simplified into that closed form by young Carl Friedrich Gauss). The mission is to find the precise maximum number of areas that the circle can be divided into (f(n)) given the number of points n.

The obvious approach is to draw some circles and see what you get. n=0 yields a boring circle, a single area. n=1 has one point but l(1)=0 (that is to say, there are no lines), so there is still just one undivided area. When f(2)=2 because there is a single line dividing it into two areas. f(3)=4, f(4)=8, and f(5)=16. It is tempting to declare that . But can you prove it? Hint: f(6)=31.

Lemma

It will later be useful to know what happens to a set of areas already divided by x lines when you run another line from one end to the other, crossing x lines (see the example where x=2). This is complex because if the x lines intersect eachother then we could chose to insert the new line such that it hits the intersection point, resulting in fewer new areas being generated by the division. However, there will generally be a path for the new line such as line {b} which does not involve more than two lines intersecting at any given point (proof?), and in this case it will generally result in the creation of x+1 (in this case 3) new spaces. Hopefully with the figure and your own intuition this is obvious, but some members of the audience may desire a more rigorous proof.

Proof

And here we go. This will be an inductive proof. That is to say that we will start at an arbitrarily small example (such as f(0)=0) and then provide a formula for f(n) in terms of f(n-1).

In the figure you can see the dark lines connecting points 1 through 4 dividing the circle into 8 total regions (i.e., f(4)=8). This figure illustrates the inductive step from n=4 to n=5 with the dashed lines. When the fifth point is added (i.e., when computing f(5) using f(4)), this results in four (n-1) new lines (the dashed lines in the diagram) being added, which I will number 1 through 4, one for each point that they connect to. The number of new regions introduced by the fifth point can therefore be determined by considering the number of reginos added by each of the 4 lines. So set i to count the lines we are adding. Each new line can cross a number of existing lines, depending on which point it is to (the value of i). The new lines will never cross eachother except at the new point because they are non-coincident lines (they contain at least one unique point, namely the other endpoint) so they have exactly one intersection and no more.

The number of lines that each new line intersects can be determined by considering the number of points on the "left" of the line and the number of points on the "right" of the line. Since all existing points already have lines between them, the number of points on the left multiplied by the number of points on the right is the number of lines that will be crossing the new line. For the line to point i, there are n-i-1 points on the left and i-1 points on the right, so a total of (n-i-1)(i-1) lines must be crossed. In this example, the lines to i=1 and i=4 each cross zero lines, while the lines to i=2 and i=3 each cross two lines (there are two points on one side and one on the other).

So the recurrence can be expressed as

Which can be easily reduced somewhat to

But it is not obvious how to get this down to a closed form (to eliminate the summation or the recurrence).

An interesting further proof might be the minimum number of regions that a circle must be divided into in order to accommodate n points in this fashion. This requires that more than two lines intersect at a single point.