The Lazy Caterer’s Sequence describes the maximum number of slices that can be made on a pizza using a given number of straight cuts. The sequence begins as follows:
| Cuts | 0 | 1 | 2 | 3 | 4 | ... |
|---|---|---|---|---|---|---|
| Slices | 1 | 2 | 4 | 7 | 11 | ... |
Intuitively, to maximize slices, each straight cut should pass through all prior cuts. Furthermore, that cut should not pass through the intersection of two prior cuts. In this way, the \(n^{th}\) cut will pass through \(n-1\) previous cuts and be divided into \(n\) segments. Each of those \(n\) segments will split an existing slice in \(2\), resulting in \(n\) new slices.
Formally, this can be expressed by the following recurrence relation, with base case \(f(0) = 1\). \(f(n)\) represents the maximum number of slices with \(n\) cuts:
\[f(n) = n + f(n-1)\]
The closed form of this recurrence can be developed using the triangle numbers:
\[\begin{split} f(n) &= n + f(n-1) \\ &= n + (n-1) + f(n-2) \\ &= n + (n-1) + (n-2) + (n-3) + \ldots + 1 + f(0) \\ &= \frac{n(n+1)}{2} + 1 \\ &= \frac{n^2 + n + 2}{2} \end{split}\]