Results 1 to 6 of 6

Math Help - Proof by Induction (Diving a Plane into regions)

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    6

    Proof by Induction (Diving a Plane into regions)

    Show that n lines separate the plane into (n^2 + n + 2) / 2 regions if no two of these lines are parallel and no three pass through a common point.

    Okay, so I have to prove this by induction. I know this works for n =1 because if we have one line, it should divide into 2 regions (1^2 + 1 + 2) / 2 = 2 right? So since I have my base, I can assume that it is true for P(n) but my problem lies in showing that P(n+1) is true. All I know is that when we have the n+1 case, we know that the region is divided into n, with the additional line. I basically don't know what to do after this point. Any help is appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by opt!kal View Post
    Show that n lines separate the plane into (n^2 + n + 2) / 2 regions if no two of these lines are parallel and no three pass through a common point.

    Okay, so I have to prove this by induction. I know this works for n =1 because if we have one line, it should divide into 2 regions (1^2 + 1 + 2) / 2 = 2 right? So since I have my base, I can assume that it is true for P(n) but my problem lies in showing that P(n+1) is true. All I know is that when we have the n+1 case, we know that the region is divided into n, with the additional line. I basically don't know what to do after this point. Any help is appreciated!
    So by induction hypothesis, how many new regions do you need from n lines to (n+1) lines?

    Then try this: Take a sheet of paper, draw some (say 5) lines such that no 3 are intersecting etc... Count the number of regions. Now draw a new line again such that no 3 are intersecting etc. And observe while drawing when this new line is creating more regions?

    More direct Hint: The new line cuts one old line and an immediate another old line. What happens to region between them?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2008
    Posts
    6
    So it seems like as you add a new line, it divides each region into 2 for each intersection made right? So since n + 1 lines is simply n lines (which we assume true from the hypothesis) and the extra line simply divides each intersection into two more regions...Is that extra line almost acting like the P(1) case? Ehh that really doesn't make sense to me though... Should I be doing anything to the original equation given? (n^2 + n + 2) /2 ? Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by opt!kal View Post
    So it seems like as you add a new line, it divides each region into 2 for each intersection made right?
    Yes! good

    Quote Originally Posted by opt!kal View Post
    So since n + 1 lines is simply n lines (which we assume true from the hypothesis) and the extra line simply divides each intersection into two more regions...Is that extra line almost acting like the P(1) case? Ehh that really doesn't make sense to me though... Should I be doing anything to the original equation given? (n^2 + n + 2) /2 ? Thanks in advance.
    No..No.. We will have P(n) regions by induction hypothesis. The new line drawn cuts each of the n old lines. For each cut between two lines, it creates an additional region.With n old lines, we can have 'n+1' new regions. Thus

    P(n+1) = P(n) + n+1 = (n^2 + n + 2) /2 + n+1 = (n^2 + 3n + 4)/2 = ((n+1)^2 + (n+1) + 2) /2
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2008
    Posts
    6
    ohhh I see, its making a region for every intersection, so it will be much more than two. Awesome, I think I get it! Thank you very much!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by opt!kal View Post
    ohhh I see, its making a region for every intersection, so it will be much more than two.
    Yes, since its making a region for every intersection, there will be as many regions as intersections plus an additional region which is made even before it cuts the first line. There are n intersections with n old lines, plus an additional region. So n+1 new regions

    Quote Originally Posted by opt!kal View Post
    Awesome, I think I get it! Thank you very much!
    No problem. Glad to be of help
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sketching regions in the complex plane
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: November 20th 2011, 06:33 PM
  2. Regions in the Complex Plane
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: September 10th 2011, 06:50 PM
  3. Sketching Regions in the Complex Plane
    Posted in the Calculus Forum
    Replies: 3
    Last Post: March 23rd 2011, 03:22 AM
  4. Sketching regions in complex plane
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: November 9th 2010, 10:30 AM
  5. diving an area into two equal regions
    Posted in the Calculus Forum
    Replies: 6
    Last Post: February 12th 2010, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum