Unexpected Patterns: Slicing Circles and Cutting Cake

1, 2, 4, 8, 16, …

What would you say the next number in the sequence is? You may feel very confident that your answer of 32 is correct. But if your friend said 31, would they be wrong?

Perhaps they forgot how to multiply by 2, in which case, you could help them out. Or perhaps, they found a different pattern from the one you found. One of the beautiful things about sequences like the one above is that although there may be an obvious next term, there is never a correct one. Without a prescribed rule, any sequence can be defined by any number of rules that would predict the next term. Consider the following three continuations of the sequence above:

a. 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, …

b. 1, 2, 4, 8, 16, 1, 2, 4, 8, 16, 1, …

c. 1, 2, 4, 8, 16, 31, 57, 99, 163, 256, …

You likely recognize the first sequence to be the powers of two, which has the formula

starting at n = 0.

The second sequence may feel like a trick. This sequence is also the powers of two, but now the pattern resets at 16. Of course this would work, but it may feel trivial. There are plenty of ways to describe this pattern but two possible formulas for this sequence are

again with both formulas starting at n = 0.

While the formulas for the second sequence may not have been as intuitive, the pattern might still feel obvious. I expect that this is not the case for most readers when they examine the third sequence. Although the pattern is not as obvious, this sequence of seemingly random numbers is still a valid continuation of the sequence. And although finding a formula to determine the next number in the sequence is not as simple as the others we’ve seen, there is a relatively simple geometric explanation for where these numbers come from. I hope to provide you with some intuition as to why this sequence works, where it comes from and how it connects a variety of ideas, from circles to number triangles to cake.

Dissecting a Circle

I’ll offer now a different question to explore. If you place n points at random on the perimeter of a circle and connect all possible pairs of points with a line segment, how many regions will there be inside the circle? I find that this is much easier if you can visualize it, so I’ve provided examples for up to n = 5 points:

I’ll refer to a circle with n points as Stage n. If you were to count the number of regions in the circles at each stage, you should come up with a table like this:

We are again faced with this sequence {1, 2, 4, 8, 16, …} and I implore you to predict what the next number in the sequence would be, i.e. how many regions would there be in a circle that is divided by n = 6 points?

One likely guess would be 32 regions. A savvy reader may remember the sequence from above and guess 31. Consider the following two iterations of stage 6:

The circle on the left has 30 regions. The circle on the right has 31. These are the two possible answers for n = 6, giving us a much more confusing table of values:

We don’t have the tools to handle a sequence that has more than one 6th term, so let’s split our table into two possible sequences: {1, 2, 4, 8, 16, 30,…} and {1, 2, 4, 8, 16, 31,…} and focus on one at a time. One question that may be worth asking is how can we get both 30 and 31 as correct answers?

If we look carefully at each of the intersections of the lines, you may notice that in the center of the left circle there are three lines that all intersect at the same point. This intersection of three lines eliminates one of the possible regions that is present in the right circle, which has no intersections between more than two lines. For the sake of simplicity, I will only consider the latter sequence, and leave the former to be explored another day.

We now have a new assumption and therefore must redefine our original question. Our new sequence now models the number of regions into which a circle is divided by n points on the circle that are connected by line segments with no more than two line segments intersecting at any point in the circle. Using counting methods, we are able to find multiple terms in the sequence, but the task of counting all regions in a circle becomes tedious very quickly for larger values of n, so finding a formula for our sequence is essential. Counting more than 99 regions for Stage 9 with accuracy quickly becomes more trouble than it is worth. Luckily for us, there is already a much easier strategy for finding a formula for our sequence of numbers.

Finite Differences: Into the weeds

The method of finite differences explores the difference between consecutive terms of the sequence. For a linear sequence like {2, 5, 8, 11,…}, the first difference between each term is 3, i.e. 5–2=3, 8–5=3, and so on. Because the first difference is constant, that means the sequence can be modeled as a first order polynomial, in particular the first order polynomial:

For a more complex pattern, where the first difference is not constant, you can then find the second difference by finding the difference between first differences, and so on. The first column that contains a constant term denotes the order of the polynomial. For our regions in a circle sequence, we come up with the following table:

In the case of our sequence, the first column that contains a constant term (1) is the fourth difference, meaning that our sequence can be modelled by a fourth order polynomial. Thus, our sequence can be modelled in the form

where each c term is a constant value. Finding a model then comes down to plugging in values for n and R(n) to solve for the constants. We find ourselves with a system of equations like this, if the first 5 terms of R(n) are used:

Putting the system into matrix form and letting MATLAB do the heavy lifting gives us the following:

Substituting these values back into our original formula produces the following equation to model our sequence:

This gives us an equation for the third sequence we considered at the beginning of the article if we start with n=1.

So far, we have given meaning to the sequence {1, 2, 4, 8, 16, 31, 57, 99, 163, 256, …} that I presented at the beginning and now we have an equation to find the next term, but I also promised triangles and cake. Although we already have our solution, I would like to explore another route to our answer, a formula that I would argue is a little more ~fun~.

No More Cooking by the Book

Not content with a final product that came from a recipe, I wanted to make mine from scratch. So I sought out another strategy for determining how many regions there would be for a given Stage n.

As I was counting the regions in the circle, I noticed that it was much easier to count how many more regions there were in a given stage compared to the previous stage. In a way, I was finding the first differences as a means to determine how many regions there would be in Stage n+1. I found that with the addition of each point, there was a relationship between the number of new lines, the number of intersections, and the number of new regions.

Some patterns appear in this table when exploring how the stages change from one to the next. First, it should make sense that the number of regions in a given stage is the sum of the regions from the previous stage and the new regions. Stage 6, for example, has 31 regions because stage 5 had 16 regions and there are 15 new regions (31 = 16 + 15). Another pattern worth noting is that the number of new regions is equal to the sum of the new lines and the new intersections. Because of these relationships, we now have an abstract recursive formula for the number of regions at Stage n:

We now can now translate the difficult task of counting regions into a new, potentially easier task: counting lines and intersections. Consider the transition from Stage 4 to Stage 5:

Starting from the new point which has been added on the right side of the circle, we can count, line by line, how many new regions have been created.

Moving counterclockwise and starting with the line labelled 1, each new line creates 1, 3, 3, 1 new regions respectively. These new regions are caused by a new line splitting a previous region in two smaller regions, every time a line segment intersects with another line segment or with the circle. Doing this for the first several stages creates a table with a pattern that may look familiar:

You may recognize this pattern as Pascal’s triangle, a famous array of numbers that somehow has the answer to everything, this question included. As has been a theme in this article, though, our pattern seems to fall apart when we consider Stage 6.

When we start counting from our new sixth point, again starting from the newest point and travelling counterclockwise, each new line creates 1, 4, 5, 4, 1 new regions.

If our Pascal’s triangle prediction had continued, the new lines should have created 1, 4, 6, 4, 1 new regions. Instead of being disappointed that our intuition has failed us once again, let’s explore this new pattern and create our own triangle. I’ve done the heavy lifting for the first 9 rows of our new triangle, as well as calculated the sum of the numbers on each row, and the sum of all numbers up to a given row:

The triangle we have created is not Pascal’s triangle, but it is certainly similar. I was not the first to discover this triangle, however, so it already has a name: the rascal triangle, named by three middle school students who discovered the formula to find any entry of the triangle. The row sums of our new triangle, as we had established previously, are the number of new regions created at each stage of our circle question, which is also the sequence of first differences that we found in our first approach. The total sum, then, is the total number of regions in the circle at a given stage, minus one, because the rascal triangle only accounts for new regions, and does not account for the starting region, i.e. the first circle.

The rascal triangle is an interesting way to visualize the number of regions in a given stage, but ultimately we are still left with a lot of counting and adding — hardly much better than drawing the circle and counting the regions. This is where cake comes in.

Cakes and Lazy Caterers

While researching the rascal triangle, I searched the number sequence in the On-line Encyclopedia of Integer Sequences (OEIS), where the rows of the rascal triangle are indexed as the sequence A077028. The entry for sequence A077028, notes that the row sums {1, 2, 4, 8, 15, 26, 42,…} go by another name: the cake numbers.

The cake numbers, C(n), are the maximum number of pieces you can cut a (cube shaped) cake into with n cuts, or in strictly math language: the maximum number of regions into which a cube can be partitioned by exactly n planes.

So you start with 1 big cube of chocolate cake, cut it once to get two slices of cake, cut it again to get 4 slices, and so on, maximizing the number of slices attained each time. So if you want your formula for how many regions there are in a circle at stage n in terms of cake numbers:

Starting at n=1, and defining C(-1)=0, we can use this equation to find the number of regions.

This isn’t simpler than the first formula we established, we’ve just reframed it again, though arguably in an even more intriguing way (if you like cake). But this way of representing our sequence reveals an interesting pattern that may reveal much more than we intended.

Before I can tie everything together, I must introduce you to one more sequence of numbers, the lazy caterer’s sequence: {1, 2, 4, 7, 11, 16, 22, 29,…}. The lazy caterer’s sequence, which I’ll denote L(n), is the two-dimensional analogue of the cake numbers, that is, instead of cutting a 3D cake, we are cutting a 2D pizza (or pancake, any flat round food item, really.)

An astute reader may notice that we have already seen the lazy caterer’s sequence, we just didn’t have a name for it. Previously we had referred to the lazy caterer’s sequence simply as the second differences of our regions in a circle sequence. Let me bring back the finite differences table from before, but this time with updated titles:

The connections to the cake numbers and lazy caterer’s sequence are fun, but also useful, as both sequences have relatively simple formulas that rely on binomial coefficients:

This leads to a new and an otherwise nonobvious formula for our regions in a circle problem:

This formula is equivalent to the fourth-order polynomial formula that we established before, and although the path we took to get here was not as straight-forward as for our first answer, that doesn’t make it any less correct.

It also introduces a brand new meaning to the sequence we’ve been exploring. If the lazy caterer’s sequence is the 2D equivalent to the cake numbers, then our regions in a circle sequence may well be a 4D equivalent of the cake numbers. The relatively straight-forward problem that we’ve been trying to solve may have greater implications for a problem that is much trickier to visualize: what is the maximum number of slices we can cut a four-dimensional hypercake into, given n cuts? It seems that we may have already found an answer for this wildly absurd but equally amusing question. 🦂

This article was adapted from an assignment for my Math for Secondary Education course. Thank you Dr. Dana Grosser-Clarkson for creating the assignment and especially for encouraging me to share my work.