I'm wondering the following: What's the maximum number of parts you can get when cutting a $D$-dimensional space with $n$ hyperplanes? The root of this questioning is that I first dicovered while studying simple neural nets for classification, that in 2D with 3 binary output neurons, where the network is just a linear classificator (no hidden layer), you can get maximum 7 classes, and not 8 (number of possible combinations of 3 binary digits) as expected.
As shown on the image, the class 010 is missing. There can also be the case where all three points intersect at the same place and we only get 6 domains but this is of fewer interest for me.
I've tried to understand what's going on in two dimensions and I figured out that you can get maximum $n+1$ new domains by adding a straight line, where $n$ designs the number of existing straight lines. It seems to work pretty fine, although I did not prove it (my bad):
For all integer $n$, let $f(n)$ be the maximum number of domains that you can get with $n$ straight lines on a plane.
$$ \text{Conjecture:}~~~~~~~~~~~\begin{cases} f(0)=1\\ \forall n>0, ~~ f(n)=n+f(n-1) \end{cases} $$
Then I tried to see how the problem looked like in higher dimensions, starting with planes in 3D but it quickly became hard to sketch on a sheet of paper. I defined another function $f_D$ that describes the maximum number of domains you get when cutting a $D$-dimensional space with hyperplanes. From hand drawings, I got the following formula (which does not hold for $n=0$ anymore):
$$ \text{Conjecture:}~~~~~~~~~~~\forall D\in \mathbb N^*, ~~ \begin{cases} f_D(1)=2\\ \forall n>1, ~~ f_D(n)=n\cdot(D-1)+f(n-1) \end{cases} $$
Which can be de-recursified (easy proof by induction) into:
$$ \forall D, n\in \mathbb N^*, f_D(n)=\frac{n^2+n-2}{2}(D-1)+2 = \frac{n\cdot(n+1)}{2}(D-1)+3-D $$
Can anyone prove or disprove my intuition? Or give me hints about how I should take the problem, or point me to existing solutions? Thanks in advance.
