Lazy caterer's sequence
The lazy caterer's sequence, more formally known as the central polygonal numbers, describes the maximum number of pieces of a disk (a pancake or pizza is usually used to describe the situation) that can be made with a given number of straight cuts. For example, three cuts across a pancake will produce six pieces if the cuts all meet at a common point inside the circle, but up to seven if they do not. This problem can be formalized mathematically as one of counting the cells in an arrangement of lines; for generalizations to higher dimensions, see arrangement of hyperplanes.
The analogue of this sequence in three dimensions is the cake number.
Formula and sequence
The maximum number p of pieces that can be created with a given number of cuts Template:Math, where Template:Math, is given by the formula
Using binomial coefficients, the formula can be expressed as
Simply put, each number equals a triangular number plus 1.
This sequence Template:OEIS, starting with Template:Math, thus results in
Proof
.gif)
When a circle is cut Template:Math times to produce the maximum number of pieces, represented as Template:Math, the Template:Mathth cut must be considered; the number of pieces before the last cut is Template:Math, while the number of pieces added by the last cut is Template:Math.
To obtain the maximum number of pieces, the Template:Mathth cut line should cross all the other previous cut lines inside the circle, but not cross any intersection of previous cut lines. Thus, the Template:Mathth line itself is cut in Template:Math places, and into Template:Math line segments. Each segment divides one piece of the Template:Math-cut pancake into 2 parts, adding exactly Template:Math to the number of pieces. The new line can't have any more segments since it can only cross each previous line once. A cut line can always cross over all previous cut lines, as rotating the knife at a small angle around a point that is not an existing intersection will, if the angle is small enough, intersect all the previous lines including the last one added.
Thus, the total number of pieces after Template:Math cuts is
This recurrence relation can be solved. If Template:Math is expanded one term the relation becomes
Expansion of the term Template:Math can continue until the last term is reduced to Template:Math, thus,
Since Template:Math, because there is one piece before any cuts are made, this can be rewritten as
This can be simplified, using the formula for the sum of an arithmetic progression:
