Configurations of hyperplanes

Question

There are 8 configurations of planes where each two intersect in a line, are parallel, or coincide. Now let $C(n)$ be number of configurations of n hyperplanes in an nxn system of linear equations. I have proven that for $n$ greater than or equal to 3 that

$C(n)= n(n+1)/2 + 1[C(n-1)-1] + 2[C(n-2)-1] + ... + (n-2)(3-1) $

(will share proof on request).

Then I found out on the net that for $n=3, 4, 5,\ldots$,

$C(n) =$ alternating numbers of the Fibonacci sequence starting from 8,

which matches the results of my formula. How is that proven, and can I prove it starting from my formula?

Answer 1

Write $f_n$ to be the number of tilings of a $1\times n$ board with $1\times 1$ squares and $1\times 2$ dominos. Recall that this the Fibonacci sequence, shifted so that $f_0=f_1=1$ (Proof: the last tile must either be a square or a domino, hence $f_n=f_{n-1}+f_{n-2}$.)

Proposition: $C(n)=f_{2n-1}$ for all $n\geq 1$.

It suffices to prove that the odd-index Fibonacci numbers satisfy your recurrence, that is, to prove that $f_{2n-1} = \frac{n(n+1)}{2} + \sum_{k=1}^{n-2} k(f_{2n-1-2k}-1)$. I'm going to start by doing some algebra on this recurrence— we can probably make an argument in its original form but I spy an easier one...

$$\begin{align*} f_{2n-1} &= \frac{n(n+1)}{2} + \sum_{k=1}^{n-2} k(f_{2n-1-2k}-1)\\ &=\sum_{k=n-1}^n k + \sum_{k=1}^{n-2} k\cdot f_{2n-1-2k} \\ &= n + \sum_{k=1}^{n-1} k\cdot f_{2n-1-2k}\\ \end{align*}$$

In the first equality we're remembering $\sum_{k=1}^n k = \frac{n(n+1)}{2}$ and so most of those terms cancel with the $-k$ in the sum. In the second equality we're noting that we can move the $k=n-1$ from the first to the second sum because $n-1=(n-1)f_{2n-1-2(n-1)}$.

This has a nice combinatorial argument. A board with length $2n-1$ either has exactly one square, or it has at least two.

• There are $n$ boards with exactly one square, since it is just a matter of where to put the square between the $n-1$ dominos.
• If it has at least two, let $k$ be the number of tiles occuring before the second square. Necessarily these must be one square and $k-1$ dominos, which may be arranged in $k$ ways and have total length $1+2(k-1)=2k-1$. The next tile must be a square by definition, and then the remaining board, having length $(2n-1)-(2k-1)-1$, can be tiled in $f_{2n-1-2k}$ ways.

Thus the right-hand side counts the number of boards of length $2n-1$, just as the left-hand side does.

---

A peek behind the curtain: I understand that this proof might look completely magic, but actually it came from somewhere. Whatever accounting method you used for the subspaces got you an "unusual" recurrence for odd Fibonacci numbers. The more typical one is $f_{2n-1}=f_{2n-3}+\cdots+f_3+f_1 = \sum_{k=1}^{n-1}1\cdot f_{2n-1-2k}$.

To prove that using tiling, we can condition on the location of the first square (which must exist!), so when I saw your sum was so similar, I was already looking for a proof of this type. But because of the $k$ in the sum I knew I needed to have a little bit of flexibility with the "first half" of the board. I realized that if I had exactly one square, that all the others would be dominos so I would get a linear number of ways to slot it in, and I just kept insisting on that interpretation and forced the details to fit into place.

Initially when I was just looking at the recurrence as you gave it, I was thinking that $-1$ would mean "ignore one special tiling" for each $k$, of which the natural one is the one with all squares. But then I saw that it was really a $-k$ and I could use it to telescope away most of the "weird" term outside the summation, and so I went that route. (Like I said, I think you could make the original form work; there's clues that I just didn't piece together. For instance, $\frac{n(n+1)}{2}$ is the number of ways to insert two squares in between $n-1$ dominos!)