Cutting space by hyperplanes: a direct proof

Question

The number of regions formed by cutting $k$ generic hyperplanes out of $\mathbb R^n$ is: $$C_n(k)=\binom{k}{0}+\binom{k}{1}+\dots+\binom{k}{n}$$ The usual proof is by induction, counting how many new regions are formed by adding the $k^\text{th}$ plane and utilizing the formula $C_n(k)=C_n(k-1)+C_{n-1}(k-1)$. This formula resembles Pascal's rule $\binom{n}k=\binom{n}{k-1}+\binom{n-1}{k-1}$ and indeed, it can be proven by rearranging sums and applying Pascal's rule.

But we can also view $C_n(k)$ as the number of subsets of $\{1,2,\dots,k\}$ of size $\leq n$. Then the formula $C_n(k)=C_n(k-1)+C_{n-1}(k-1)$ admits essentially the same combinatorial proof as Pascal's rule, where we break up $C_n(k)$ depending on whether or not the subset contains $k$.

To better understand the relationship between $C_n(k)$ and hyperplane cutting, I wonder if there is a direct proof (i.e. not using induction) of the above-mentioned result? Since there are $k$ hyperplanes, it seems reasonable that $C_n(k)$ might count subsets of these hyperplanes of size $\leq n$. But the question that currently stumps me is: how does one then biject these subsets of the planes with the regions?

Answer 1

Choose coordinates for $\mathbb R^n$ so none of the $k$ hyperplanes are parallel to any coordinate planes, and so that all of the hyperplane intersections occur in the orthant where all coordinates are positive.

First, we account for the $\binom{k}n$ term. Any $n$ of the $k$ hyperplanes will intersect in a point, and that point will be the "lowest" point of one of the regions, where "lowest" means having the least $x_1$ coordinate. Conversely, any region with a lowest point determines a set of $n$ hyperplanes intersecting at that point.

The only regions which have not been accounted for are those which do not have a lowest point. To count these, let $E_1$ be the coordinate plane perpendicular to the $x_1$ axis, so by assumption all the intersection points are above $E_1$. Then the original regions with no lowest point correspond to the regions $E_1$ is divided into by the $k$ planes. Since the dimension of $E_{1}$ is one less than $\mathbb R^n$, you can recursively give a bijection of subsets of size at most $n-1$ of the $k$ planes with the regions of $E_{1}$.

All in all, the bijection between regions of $\mathbb R^n$ and subsets of the $k$ planes of size at most $n$ is as follows:

If the size of the subset is $i$, then find the intersection $P$ of that subset of planes with the first $n-i$ coordinate planes, $E_1,E_2,\dots,E_{n-i}$, where $E_j=\{(x_1,\dots,x_n):x_j=0\}$. There is a unique region of $\mathbb R^n \cap E_1\cap \dots \cap E_{n-i}$ which has $P$ as its furthest point in the direction of the negative $x_{n-i}$ axis, and this is contained in a unique region of $\mathbb R^n$.