Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Circle Proof

  1. Jun 17, 2007 #1
    1. The problem statement, all variables and given/known data

    Suppose that [tex] n [/tex] 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 [tex] a_n [/tex] be the number of regions into which the interior of the circle is divided. Draw diagrams to find [tex] a_n [/tex] is given by the following formula [tex] 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} [/tex].

    2. Relevant equations

    Maybe use strong induction or [tex] P(n \leq k) \Rightarrow P(k+1) [/tex]

    3. The attempt at a solution

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

    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 [tex] a_n = 1,2,3 \ldots 6 [/tex] (i.e. [tex] 1, 2, 4, 8, 16, 31, 57, 99, 163 [/tex]). But then the "powers of two" pattern ends after [tex] n = 5 [/tex]. 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?

    Last edited by a moderator: May 2, 2017
  2. jcsd
  3. Jun 17, 2007 #2


    User Avatar
    Science Advisor

    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.
  4. Jun 17, 2007 #3
    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?

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook