Circle Proof Homework: Finding the Number of Regions with Induction

[tronter]

Homework Statement

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}.

Homework Equations

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

The Attempt at a Solution

Here is what I drew: http://uploadimages.com/view.php?type=thumb3&p=2007/0081/11820544788596.jpg"

I think strong induction is just a special case of regular induction. So really we can always use strong induction. I can't 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

 

[HallsofIvy]

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)ⁿ.

 

[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