Results 1 to 13 of 13

Math Help - Tricky Induction

  1. #1
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307

    Tricky Induction

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

    I am pretty sure that I can do the induction part. I tried plugging in  n = 2,3 and the number of regions were 2 and 4. The diagrams also had 2 and 4 regions respectively. But when I plugged in  n = 4  a_n = 8 . However, when I drew it I got  a_n = 9 .

    Here are the circles:

    Am I drawing the points wrong in the third circle?
    Attached Thumbnails Attached Thumbnails Tricky Induction-circles.jpg  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    actually I think I know what I am doing wrong. I was overconnecting points.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    Also, I think depending on where you put the points  a_n will be different?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2007
    From
    Marina, California
    Posts
    2

    Point locations and connections

    I believe that the points in your diagrams would lie along the perimeter of the circle, not inside of it. Also, your formula works when each point is connected to every other point, so in your n=4 diagram, there would be a total of 6 lines. Doing that, my n=2,3,4 worked out to the desired number of regions. Hope that helps a little!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    To prove the inductive step is it as simple as just plugging in   k+1 for   a_k ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2007
    From
    Marina, California
    Posts
    2

    counterexample?

    I'm actually having difficulty proving this, since I can't seem to figure out how it's true. Have you tried n=6? When I plug it into the formula, I get 31, but when I actually draw it out, I get 30 areas. (I encountered this while exploring the powers of two pattern, did you notice that?) Maybe I'm not clear on the definition of concurrent lines, but I just took that part of the problem to mean that no two lines connected the same two points. Any new thoughts?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    Here are the drawings I got:

    I think the concurrent lines mean that no three lines intersect. I got 31 for   n = 6

    Yeah the pattern was:1,2,4,8,16,31,57,99,163. We might have to use strong induction. But I cant see how  a_{k-1} and  a_k relate to  a_{k+1} . Seeing that there is no pattern, I was wondering if this is valid.

    Our induction hypothesis is:  a_{k} = k + \binom{k-1}{2} + \binom{k-1}{3} + \binom{k-1}{4} = 1 + \frac{k(k-1)(k^{2}-5k+18)}{24} for  n \leq k points joined in pairs. It really doesnt matter if we use strong induction or not, since regular induction is just a special case of strong induction. So our goal is to show that  a_{k} = k + \binom{k-1}{2} + \binom{k-1}{3} + \binom{k-1}{4} = 1 + \frac{k(k-1)(k^{2}-5k+18)}{24}  \Rightarrow  a_{k+1} = k+1 + \binom{k}{2} + \binom{k}{3} + \binom{k}{4} = 1 + \frac{(k+1)k((k+1)^{2}-5(k+1)+18)}{24}

    So then would it be valid to substitute  k+1 for  k ? I dont think we can do this since we have to use the induction hypothesis.

    Is this valid:  a_{k+1} = a_{k} + \frac{1}{6}k^{3} - \frac{1}{2}k^{2}+\frac{4}{3}k ?
    Attached Thumbnails Attached Thumbnails Tricky Induction-circleds.jpg  
    Last edited by tukeywilliams; June 17th 2007 at 12:04 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    To get  P(k) \Rightarrow P(k+1) we need to use the inductive hypothesis. Maybe we have to use the definition of the binomial coefficient:  \binom{n}{r} = \frac{n!}{r!(n-r)!} ?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    anybody know how to prove the inductive step?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    I have an inkling that strong induction is needed, but cant see the relationships.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    The correct formula is given here.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    Isnt the formula that I gave also correct?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    I know why nobody can answer this. This is a very difficult problem I believe.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Tricky induction proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 17th 2009, 09:37 PM
  5. Replies: 5
    Last Post: May 30th 2008, 06:24 AM

Search Tags


/mathhelpforum @mathhelpforum