I am trying to prove, in a combinatorial way, this identity for fibonomial coefficients, when $0\lt k \lt n $:
$${n \choose k}_F = F_{n-k+1}{n-1 \choose k-1}_F+F_{k-1} {n-1 \choose k}_F$$
where $F_n$ is defined by $F_n=F_{n-1}+F_{n-2}$, $\,\,\,F_0=0, \,\,\,\,F_1 =1$ and $${n \choose k}_F = \frac{n!_F}{k!_F(n-k)!_F}, \,\,\,\,\,\,\,\,\,\,n!_F=F_1F_2\dots F_n$$
It's well known that the $F_n$ counts the number of coverings of a board $(n-1)\times1$ with squares and dominoes and I have already proved that $F_n = F_{n-k+1}F_{k-2}+F_{k-1}F_{n-k}$ by considering when the $(k-1)$th slot of the board is covered either with one or the other kind of tile.
It's clear that the fibotorial $n!_F$ enumerates the number of tilings, with squares and dominoes, of a upper-triangular board $(n-1)\times(n-1)$ and, it has been quite harder, but I showed that the fibonomial is an integer number by "cutting away" the number of coverings of a $(k-1)\times(k-1)$ upper triangular board from $n!_F$.
Now I want to conclude that ${n-1 \choose k-1}_F = F_{k-2}$ and ${n-1 \choose k}_F =F_{n-k}$ by assembling the two results, I can do that algebraically, but how to see it in a combinatorial way?
Best Answer
Here is a combinatorial interpretation of $\binom{n}{k}_F$. All of this is taken from the source cited at the end. Quoting Theorem $2$ from the article,
This interpretation can be proved by induction, using the identity ${n \choose k}_F = F_{n-k+1}{n-1 \choose k-1}_F+F_{k-1} {n-1 \choose k}_F$, which is proved by conditioning on whether the lattice path ends with a vertical step or horizontal step.