A question about the proof of the “Lazy caterer's sequence”
In https://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence , Wiki provides formulas:-
The maximum number p of pieces that can be created with a given number of cuts n, where n ≥ 0, is given by the formula
$$p = \dfrac {n^2 + n + 2}{2}$$
Using binomial coefficients, the formula can be expressed as
$$p = {n+1 \choose 2} + 1 = {n \choose 2} + {n \choose 1} +{n \choose 0}$$
It proves the first in great details but says very little about the second and the third. I would like to know the missing details.
Best Answer
Let the lines end at the rim of the pizza. Not counting the exterior of the pizza we have, according to Euler's formula, $$f-e+v=1\ ,$$ where $f$ is the number of faces, $e$ the number of edges, and $v=v_3+v_4$ the number of vertices in the resulting configuration. If no three cuts go through the same point there are $v_3=2n$ vertices of degree $3$ along the rim of the pizza and $v_4$ vertices of degree $4$ in its interior. From $2e=3v_3+4v_4$ it follows that $e=3n+2v_4$. Inserting this into $(1)$ we therefore obtain $$f=3n+2v_4-(2n+v_4)+1=v_4+n+1\leq{n\choose 2}+{n\choose 1}+{n\choose0}\ ,$$ with equality iff we take care that all ${n\choose2}$ intersection points of the cuts are within the pizza.