1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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: 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 [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?

    Thanks
     
    Last edited: Jun 17, 2007
  2. jcsd
  3. Jun 17, 2007 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    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?

    Thanks
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Circle Proof
  1. Curvature Circle Proof (Replies: 0)

  2. The circle (Replies: 2)

Loading...