Circle Proof

1. Jun 17, 2007

tronter

1. The problem statement, all variables and given/known data

Suppose that $$n$$ points lie on a circle are all joined in pairs. The points are positioned so that no three joining lines are concurrent in the interior of the circle. Let $$a_n$$ be the number of regions into which the interior of the circle is divided. Draw diagrams to find $$a_n$$ is given by the following formula $$a_n = n + \binom{n-1}{2} + \binom{n-1}{3} + \binom{n-1}{4} = 1+ \frac{n(n-1)(n^{2}-5n+18)}{24}$$.

2. Relevant equations

Maybe use strong induction or $$P(n \leq k) \Rightarrow P(k+1)$$

3. The attempt at a solution

Here is what I drew: Here

I think strong induction is just a special case of regular induction. So really we can always use strong induction. I cant seem to find a pattern.

There seems to be a pattern for $$a_n = 1,2,3 \ldots 6$$ (i.e. $$1, 2, 4, 8, 16, 31, 57, 99, 163$$). But then the "powers of two" pattern ends after $$n = 5$$. So I am not sure strong induction could be used.

But how would I prove the inductive step? Would I use the definition of the binomial coefficient?

Thanks

Last edited: Jun 17, 2007
2. Jun 17, 2007

HallsofIvy

Staff Emeritus
Proving that the formula is correct is a very hard problem. If I remember correctly, you use Euler's formula: if a diagram in the plane has v vertices, f faces, and s sides, then v- s+ f= 2. If you add one more point on circle and draw all lines to other points, how many of those previous lines will they cross? how many new "sides" and "vertices" will that produce?

You might recognize that formula using binomial coefficients as part of the "binomial theorem"- the first four coefficients of (x+ y)n.

3. Jun 17, 2007

tronter

This was given as a problem in a book I am self studying from. So it is a pretty hard problem then? Would students be expected to do this?

Thanks