Cut circle with straight lines

Question

Problem: To cut a circle with $n$ straight lines into the greatest number of possible parts.

What is the greatest number and how can you prove it is optimal?

Answer 1

the number of parts is $\binom{n}{2}+\binom{n}{1}+\binom{n}{0}$

I'll give you a hint first, consider what happens when you add a new line to the circle. How many lines intersect it? and how many new parts does that create?

Note that this problem generalizes to $n$ planes cutting a sphere: for that, the number of parts would be $\binom{n}{3}+\binom{n}{2}+\binom{n}{1}+\binom{n}{0}$. Use recursion to prove and by using the formula for the original problem.

Answer 2

Make the $n$th line cross $n-1$ lines to get the maximal number of partitions. The first division gives $2$ of course, the second line $4$, and the $3$rd line $7$. For the $4$th line you get $11$ sections by this algorithm:

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$

For each $n$, you add $n-1$ sections, so the total number of sections is: $$2 + 2 + 3 + 4 + \ldots = \frac{n^2 + n + 2}{2}$$ This sequence is A000124.