Mathematical Induction Question involving circles

[Jefferson]

Could someone please help me with the following question thanks!

Prove by mathematical induction that the greatest number of regions that a circle can be divided into by n straight lines is (1/2)(n²+n+2) for all positive n integers.
 

[RuiAce]

To understand this question (which is also well beyond the scope of MX1), you should start with some test cases.

When \(n=1\) the expression equals \(2\)
When \(n=2\) the expression equals \(4\)
When \(n=3\) the expression equals \(7\)

Start with a circle and draw only 1 line through it. It's quite obvious that there are 2 regions, so this is unsurprising.

Now start with a circle and draw exactly 2 lines through it. You should see that if the lines do not intersect inside the circle (i.e. along the circumference, or outside the circle), you'll end up with 3 regions. But if the lines intersect inside the circle, you'll end up with 4 regions. So we see that the number 4 is attainable.

For the sake of the inductive assumption, we're always assuming that we have the maximum number of regions at \(n=k\). So we'll assume that when \(n=2\) we have 4 regions, and see if we can prove that when \(n=3\) we have 7 regions.

Start with a circle with 2 lines through it, such that those two lines intersect inside the circle. There are two ways of drawing a third line through it.
- We can draw the line so that it is concurrent with the other two, i.e. all 3 lines intersect at the same point. If you do this, you'll see that you end up with 6 regions.
- We can draw the line so that it is not current with the other two, and as a consequence we end up with \( \binom32 = 3\) distinct points of intersection. If you do this, you'll see that you end up with 7 regions.
(Note that, as we've established above we always want the lines to intersect.)

So again, the number of 7 is attainable. But what's really going on when we draw this third line? Where does the actual induction come into play?

Draw a circle with 2 lines through it so that we have 4 regions again. Start drawing the third line, but stop when it bumps into one of the two other lines. What have you really done? You've actually split one region into two (smaller) regions (and hence you now have 5 regions).
Now keep drawing that line until you reach the second line. Note that you've split another region into two (smaller) (and hence you now have 6 regions).
And finally keep drawing until you reach the circumference of the circle again. Again, one region has been split into two, so there's our 7 regions as required.

By thinking of it this way, we now understand how the inductive step works. So this is the proof.
\[ \text{When }n=1\text{, we note that any circle is always divided into 2 regions by a line through it}\\ \text{and the expression also equals 2, so the statement holds.} \]
\[ \text{Assume that given a circle, the greatest number of regions a circle can be divided}\\ \text{by }\textbf{any }k\text{ straight lines is }\frac12 (k^2+k+2).\]
\[ \text{We construct the scenario where we have }k+1\text{ straight lines dividing a circle.}\\ \text{Consider a circle with }k+1\text{ lines dividing it, and assume the maximum number of regions.}\]
\[ \text{Single out 1 line and consider the remaining }k\text{ lines. They should also}\\ \text{split the circle into the maximum number of regions possible, which}\\ \text{by assumption is }\frac12(k^2+k+2).\]
Note that if the \(k+1\) lines divide the circle in the maximum number of lines possible for \( n=k+1\), then the same should occur for the \(k\) lines in the case \(n=k\). Otherwise, those \(k\) lines could be somehow changed (for example rotated) to give us more regions, which would then give us more regions when we add in that \((k+1)\)-th line as well.
\[ \text{For maximality, we can force the last line to intersect each of the other }k\text{ lines}\\ \text{at distinct points for each line, thereby introducing }\\ k+1\text{ new regions.}\]
This guarantees maximality, because one less region would be introduced each time we have 3 concurrent lines.
\[\text{Hence the maximum number of regions is given by}\\ \begin{align*} \frac12 (k^2+k+2) + (k+1) &= \frac12 (k^2+k+2+2k+2)\\ &= \frac12 ((k+1)^2 + (k+1) + 2) \end{align*}\\ \text{as required.} \]
Again, as this is beyond the scope of the course, I will not address questions of a similar calibre without a reasonable attempt.

[Jefferson]

To understand this question (which is also well beyond the scope of MX1), you should start with some test cases.

When \(n=1\) the expression equals \(2\)
When \(n=2\) the expression equals \(4\)
When \(n=3\) the expression equals \(7\)

Start with a circle and draw only 1 line through it. It's quite obvious that there are 2 regions, so this is unsurprising.

Now start with a circle and draw exactly 2 lines through it. You should see that if the lines do not intersect inside the circle (i.e. along the circumference, or outside the circle), you'll end up with 3 regions. But if the lines intersect inside the circle, you'll end up with 4 regions. So we see that the number 4 is attainable.

For the sake of the inductive assumption, we're always assuming that we have the maximum number of regions at \(n=k\). So we'll assume that when \(n=2\) we have 4 regions, and see if we can prove that when \(n=3\) we have 7 regions.

Start with a circle with 2 lines through it, such that those two lines intersect inside the circle. There are two ways of drawing a third line through it.
- We can draw the line so that it is concurrent with the other two, i.e. all 3 lines intersect at the same point. If you do this, you'll see that you end up with 6 regions.
- We can draw the line so that it is not current with the other two, and as a consequence we end up with \( \binom32 = 3\) distinct points of intersection. If you do this, you'll see that you end up with 7 regions.
(Note that, as we've established above we always want the lines to intersect.)

So again, the number of 7 is attainable. But what's really going on when we draw this third line? Where does the actual induction come into play?

Draw a circle with 2 lines through it so that we have 4 regions again. Start drawing the third line, but stop when it bumps into one of the two other lines. What have you really done? You've actually split one region into two (smaller) regions (and hence you now have 5 regions).
Now keep drawing that line until you reach the second line. Note that you've split another region into two (smaller) (and hence you now have 6 regions).
And finally keep drawing until you reach the circumference of the circle again. Again, one region has been split into two, so there's our 7 regions as required.

By thinking of it this way, we now understand how the inductive step works. So this is the proof.
\[ \text{When }n=1\text{, we note that any circle is always divided into 2 regions by a line through it}\\ \text{and the expression also equals 2, so the statement holds.} \]
\[ \text{Assume that given a circle, the greatest number of regions a circle can be divided}\\ \text{by }\textbf{any }k\text{ straight lines is }\frac12 (k^2+k+2).\]
\[ \text{We construct the scenario where we have }k+1\text{ straight lines dividing a circle.}\\ \text{Consider a circle with }k+1\text{ lines dividing it, and assume the maximum number of regions.}\]
\[ \text{Single out 1 line and consider the remaining }k\text{ lines. They should also}\\ \text{split the circle into the maximum number of regions possible, which}\\ \text{by assumption is }\frac12(k^2+k+2).\]
Note that if the \(k+1\) lines divide the circle in the maximum number of lines possible for \( n=k+1\), then the same should occur for the \(k\) lines in the case \(n=k\). Otherwise, those \(k\) lines could be somehow changed (for example rotated) to give us more regions, which would then give us more regions when we add in that \((k+1)\)-th line as well.
\[ \text{For maximality, we can force the last line to intersect each of the other }k\text{ lines}\\ \text{at distinct points for each line, thereby introducing }\\ k+1\text{ new regions.}\]
This guarantees maximality, because one less region would be introduced each time we have 3 concurrent lines.
\[\text{Hence the maximum number of regions is given by}\\ \begin{align*} \frac12 (k^2+k+2) + (k+1) &= \frac12 (k^2+k+2+2k+2)\\ &= \frac12 ((k+1)^2 + (k+1) + 2) \end{align*}\\ \text{as required.} \]
Again, as this is beyond the scope of the course, I will not address questions of a similar calibre without a reasonable attempt.

Thank you so much for taking the time to answer this question. I did not imagine it to be this difficult.
Everything makes perfect sense now. As noted, I will include my own attempt for future references and try to provide the source's solution if applicable.
Again, thank you .