How do I create an explicit equation for this?

Question

What is the maximum number of regions into which 1 chord can divide a circle? 2 chords? 3 chords? 20 chords? Find an explicit equation relating the number of regions to the number of chords, n.

the formula for an explicit equation: f(n)=f(1)+d(n-1) the table created from this information shows a quadratic relationship so how would i create an explicit equation? I know there is a method called the brute force method but i do not know how to use it

Answer 1

Once you know it is quadratic, you have $f(n)=an^2+bn+c$. Compute $f(1), f(2), f(3)$. Now you can write $f(3)=a\cdot 3^2+b\cdot 3+c$ and two similar equations. Solve them simultaneously for $a,b,c$

Answer 2

This is a nice result sometimes known as the "pancake cutting problem" or "lazy caterer problem". Let $k$ denote the number of cuts and $f$ be the function that maps a number of cuts $k$ to the corresponding maximum number of regions created by performing $k$ cuts $f(k)$.

When in doubt it's useful try a first few examples. Getting our hands dirty we find \begin{align*} f(1) &= 2 \\ f(2) &= 4 \\ &= 2 + f(1) \\ f(3) &= 7 \\ &= 3 + f(2) \\ &= 3 + 2 + f(1) \\ f(4) &= 14 = 4 + f(3) \\ &= 4 + 3 + 2 + f(1) \end{align*}

We're starting to get the sneaking suspicion that the general rule for $k$ cuts can be given by \begin{equation*} f(k) = k + f(k - 1) \end{equation*}

To see that this is indeed the case it's useful to sketch a few of our examples so that we may build a geometric argument. Suppose we have already have $k$ cuts diving our circle (in any way, not necessarily into a maximal number of regions). The next $(k + 1)th$ cut will at most intersect the previous $k$ cuts, each at a single point. Every time the $(k + 1)$th cut intersects an older cut it splits the region in two generating an additional region. Before reaching the other side of the circle the $(k + 1)$th cut will have intersected $k$ lines and so the $(k + 1)th$ cut will have created another $k$ regions. When the $(k + 1)th$ cut finally reaches the other side of the circle it will have split this final region in two and create another region. That is, the $(k + 1)$ will have created $k + 1$ new regions in total.

Constructing that argument was the hard part. We can now use some algebra to arrive to a solution. \begin{align*} f(k) &= k + f(k - 1) \\ &= \sum^k_{l = 2} l + f(1), \quad k \geq 2 \\ &= \sum^k_{l = 2} l + 2 \\ &= \sum^k_{l = 1} l + 1 \\ &= \frac{k(k + 1)}{2} + 1 \\ &= \frac{k^2 + k + 2}{2} \end{align*}

where the second to last step is a well-known result (partial sum of the first $k$ integers).