# 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)

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.
• A question to fill a gap in my knowledge. The last sentence seems to imply the empty subspace, which we get as an intersection of $k=d+1$ hyperplanes in a generał position, has dimension $-1$. Is it correct? Just curious, I've never seen a dimension assigned to an empty space. – CiaPan Apr 18 at 6:15
• @CiaPan I have wondered about it too, I guess that dimension of $-1$ means the empty set. – J. Doe Apr 18 at 9:28
• Please see the expanded answer. – CiaPan Apr 18 at 10:00

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)}$$