Problem
How many slices of pizza can a person obtain by making n straight cuts with a pizza knife?
What is the maximum number \( L_n \) of regions defined by n lines in the plane?
Solution
The nth line (for n > 0) increases the number of regions by k if and only if it splits k of the old regions, and it splits k old regions if and only if it hits the previous lines in k-1 different places. Two lines can intersect in at most one point. Therefore the new line can intersect the n-1 old lines in at most n-1 different points, and we must have \( k \leq n \). We have established the upper bound
\( L_n \leq L_{n-1} + n, \qquad \text{for n>0. } \)
Furthermore it’s easy to show by induction that we can achieve equality in this formula. We simply place the nth line in such a way that it’s not parallel to any of the others (hence it intersects them all), and such that it doesn’t go through any of the existing intersection points (hence it intersects them all in different places).
recurrence relation
\( L_0=1; \)
\( L_n=L_{n-1}+n, \qquad \text{for n>0. } \)
Simply put, each number equals a triangular number plus 1.
In other words, \( L_n \) is one more than the sum \( S_n \) of the first n positive integers.
\( L_n = \frac{1}{2}n(n+1)+1 \)