What follows is an attempt to prove the correctness of a formula for the maximum number of regions created within a circle by connecting with all possible chords n points selected around the circumference. This is an interesting problem, because for n = 1, 2, 3, 4, and 5 the formula # regions = 2^(n-1) is correct. However, just when everyone is ready to say that the correct number of regions for 6 points is 32, the actual value is 31 and the tyro's faith in mathematical induction is shattered. However, the process that has been used is not mathematical induction at all, but rather a form of inductive reasoning which is very common and very useful, while being also very dangerous.

Mathematical induction is usually reserved for study by a select few at the high-school level and may even then be poorly presented and even more poorly understood. A rigorous presentation of proof by mathematical induction requires that at least some formal development of the natural numbers has been undertaken, at least to the extent of introduction to something like the Peano postulates. Without this, proof by mathematical induction becomes just a set of steps which when carried out successfully, someone says O.K. Proofs by mathematical induction applied to physical or geometrical situations, become even more questionable, since there then must be some usually un-stated assumption that the physical or geometrical system being studied is correctly modeled by some set of natural numbers.

I will thus undertake to do my proof without using mathematical induction except when absolutely necessary.

By direct observation one can see that the maximum number of regions created using 1 point is 1, 2 points yield 2 regions, 3 points yield 4 regions. I claim that the number of additional regions added when the n point is added will be given by (n-1,1) + (n-1,3). I use the (a,b) here to indicate the binomial coefficient in the (b+1)st position in the (a=1)st row of the Pascal triangle. This is also defined by a!/b!(a-b)! and is the number of distinct subsets of size b from a set of a elements.

When the n th point is added, for n>3 , we will note the manner number of additional regions which result in two distinct parts of the diagram.

First, the new point must lie between two previously placed points, which

we denote by x and y. The previously existing region defined by the chord xy and the arc xzy has now been cut up into a number of regions which is given by n. One region has been replaced by n. The number of new regions in this part of the diagram is n-1 ands we note that n-1 = (n-1,1).

The remaining part of the original diagram, that which lies on the other side of the chord xy has also acquired new regions. This count is somewhat trickier, but if we consider the previous figure to be transformed into the one which includes the new point z, we note that one new region is created each time a previously existing chord is crossed. This happens exactly as many times as there are sets of previously existing sets of three selected points on the circumference. If {r,s,t} is such a set of three points we may assume that they occur in the order z, r, s, t as one moves in a clockwise fashion around the circumference. The new chord zs must intersect the previously existing chord rt, signaling the division of some previously existing region (involving some segment of the chord rt) into two regions.

It is important to note that each such new region involves the new chord emanating from z cutting some previously existing chord rt on its way to some previously selected point s thus corresponding to exactly one subset {r,s,t} of the previously selected points and that each such triple of previously selected points contributes exactly one new region. This argument does not depend on n and holds as long as n>3. This fact eliminates the need for an induction proof at this point.

We are assuming however that since we are only considering a finite number of selected points, and that there can only be a finite number of intersections of chords within the circle, that we may always jiggle a new point into a location so that none of its resulting chords will intersect any of the previously existing intersections. This is necessary in order to ensure that the number of regions created be maximum.

{How do we know that a global maximum is created by maximizing at each stage?}

We note that the number of such triplet subsets of the set of n-1 previously selected points is just (n-1,3). By adding the number of new regions in each of the two parts of the original diagram we see that the correct number is:

.

Now we know the answers for the small numbers of selected points 1,2, and 3 by direct observation, and that the number of new regions at each stage is as given above, we see that the total number of regions for n>3 points is:

.

In fact, our formula may be extended to work for any number of points down to 2 if we write

and follow the convention that (a,b) = 0 if a<b.

Now observe that

.

The third to last step requires induction, but may be convincingly demonstrated through a diagram instead.

Also

Thus our formula for the maximum number of regions determined by n points around the circumference of a circle may be expressed either by

or by the equivalent

.

Using the well known relations within the Pascal Triangle, that

,

and that for any a > 0, we see that our formula becomes: