# Proof by Induction (Diving a Plane into regions)

• Apr 23rd 2008, 07:59 PM
opt!kal
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!
• Apr 23rd 2008, 08:41 PM
Isomorphism
Quote:

Originally Posted by opt!kal
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?
• Apr 23rd 2008, 09:07 PM
opt!kal
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.
• Apr 23rd 2008, 09:42 PM
Isomorphism
Quote:

Originally Posted by opt!kal
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
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
• Apr 24th 2008, 03:32 AM
opt!kal
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!
• Apr 24th 2008, 04:03 AM
Isomorphism
Quote:

Originally Posted by opt!kal
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
Awesome, I think I get it! Thank you very much!

No problem. Glad to be of help :)