Understanding a step in an inductive proof that $n$ hyperplanes in $\mathbb{R}^d$ determine $\sum_{0\leq i\leq d}\binom{n}{i}$ cells ($d$-faces)

Question

In the book Lecture Notes on Discrete Geometry by Jirka Matousek, in page 127, a theorem is proved:

The number of cells ($d$-faces) in a simple arrangement of $n$ hyperplanes in $\mathbb{R}^d$ equals $\Phi_d(n)=\sum_{0\leq i\leq d}\binom{n}{i}$.

They prove it for $n=d=1$, assume the equation for dimension $d$ with $n-1$ hyperplanes. The step I don't understand is:

Since we assume general position, the $n-1$ previous hyperplanes divide the newly inserted hyperplane $h$ into $\Phi_{d-1}(n-1)$ cells by the inducative hypothesis.

Why is it true?

Clarifications:

• For a finite set of hyperplanes $H$ in $\mathbb{R}^d$, the cells of $H$ are the connected components of $\mathbb{R}^d \setminus \bigcup H$.
• $H$ is in a simple arrangement if and only if $H$ is in a general position, which means that the intersection of every $2\leq k\leq d+1$ hyperplanes is $d-k$-dimensional.

Answer 1

Apparently the part you quote explains an inductive step over $n$, a number of hyperplanes.

Consider a 2D case first: in a general configuration the $n$-th line (1D hyperplane) intersects $n-1$ previous lines and those points (zero-dimensional) of intersections dissect the line into $n$ segments - 1D cells. Each of those segments corresponds to some polygonal cell on the plane, defined by the previous $n-1$ lines, and it dissects that polygon into two. So when constructing the configuration by adding lines, the $n$-th increment in the number of 2D cells of the plane equals the $(n-1)$-st number of 1D cells.

Then 3D: the number of solids - 3D cells in a space, added by the $n$-th 2D plane equals a number of 2D polygonal cells defined by $n-1$ lines - 1D intersections of the plane with previous planes. Each of those polygons corresponds to a single polyhedral cell of the 3D space, which becomes dissected into two by the $n$-th plane.

And generally, when you add the $n$-th, $(d-1)$-dimensional hyperplane to a configuration of $n-1$ hyperplanes in a $d$-dimensional space, you get on the new hyperplane a configuration of $n-1$, $(d-2)$-dimensional intersections with previous hyperplanes. Then each of $\bbox[lightgray]{\Phi_{d-1}(n-1)}$ cells on the $n$-th hyperplane dissects one cell in the $d$-dimensional space into two, adding $1$ to a number of cells. Hence $$\Phi_d(n) = \Phi_d(n-1) + \bbox[lightgray]{\Phi_{d-1}(n-1)}$$