# “Oddity” of Fibonacci-Catalan numbers

As a follow up to my previous two MO questions, here and here, let's consider the below inquiry.

Define the Fibonacci-Catalan numbers by $$FC_n=\frac1{F_{n+1}}\binom{2n}n_F$$ where $$F_0=0, F_1=1, F_0!=1$$, $$F_n=F_{n-1}+F_{n-2} \qquad F_n!=F_1\cdot F_2\cdots F_n, \qquad \binom{n}k_F=\frac{F_n!}{F_k!\cdot F_{n-k}!}.$$

Recall the property that the Catalan numbers $$C_n=\frac1{n+1}\binom{2n}n$$ satisfy: $$C_n$$ is odd iff $$n=2^j-1$$ for some $$j\in\mathbb{N}$$. In the same vain,

QUESTION. For $$n\geq2$$, is this true? $$\text{FC_n is odd iff n=3\cdot2^j-1 for some j\in\mathbb{N}}.$$

POSTSCRIPT. In response to Alexander Burstein question below, I suppose the following should hold. If we write $$F$$ for $$F(s,t)$$ and $$FC_n(s,t)=\frac1{F_{n+1}(s,t)}\binom{2n}n_F$$ then $$\text{FC_n(2s-1,2t-1) is odd iff n=3\cdot2^j-1} \qquad \text{and}$$ $$\text{FC_n(2s,2t-1) is odd iff n=2^j-1}.$$

• I think, $FC_1=1$ and $n=1$ is not of this form – Fedor Petrov Mar 27 '19 at 2:18
• That is right, I was meaning to write $n>1$. Thanks. – T. Amdeberhan Mar 27 '19 at 3:07
• What would be a good generalization of this (non)divisibility property for Fibonacci polynomials? I.e. $F_n=F_n(s,t)$, and $F_0=0$, $F_1=1$, $F_n=sF_{n-1}+tF_{n-2}$ for $n\ge 2$, and the rest defined as above. – Alexander Burstein Mar 28 '19 at 4:19
• @AlexanderBurstein: That's a good question, please look at the above update. – T. Amdeberhan Mar 28 '19 at 16:35
• @T.Amdeberhan Thanks, that looks interesting. To follow up on this, what would be the combinatorial interpretation of that using the Sagan-Savage interpretation of the Fibonomials? (See arxiv.org/pdf/0911.3159.pdf) – Alexander Burstein Mar 29 '19 at 3:49

Let $$\alpha=(1+\sqrt{5})/2,\beta=(1-\sqrt{5})/2$$, then by Binet formula for Fibonacci numbers we have $$F_n=(\alpha^n-\beta^n)/(\alpha-\beta)=:P_n(\alpha,\beta)$$. Factorize our Catalan-like expression onto cyclotomics: $$\frac{\prod_{j=1}^{2n} P_j(x,y)}{\prod_{i=1}^{n+1}P_i(x,y)\cdot \prod_{i=1}^{n}P_i(x,y)}=\prod_{s\geqslant 2} (\Phi_s(x,y))^{\eta(n,s)},\quad (\star)\\ \text{where}\quad\eta(n,s)=\left[\frac{2n}s\right]-\left[\frac{n}s\right]-\left[\frac{n+1}s\right].\quad (\bullet)$$ Here $$\Phi_s(x,y)$$ are homogeneous cyclotomic polynomials, and $$(\star)$$ immediately follows from $$P_j=\prod_{d|j,d>1} \Phi_d$$.

Therefore we get $$FC_n=\prod_{s>2} (\Phi_s(\alpha,\beta))^{\eta(n,s)}.$$

Now let us find out which numbers $$g_s:=\Phi_s(\alpha,\beta)$$ are even. Recall that $$F_n$$ is even if and only if $$n$$ is divisible by 3. Since $$F_n=P_n(\alpha,\beta)=\prod_{d|n} \Phi_d(\alpha,\beta)=\prod_{d|n} g_d,$$ we conclude that $$g_s$$ are odd when $$s$$ is not divisible by 3. Next, if $$n=3kl$$ for odd $$l>1$$, then $$g_{3kl}$$ divides $$\frac{F_{3kl}}{F_{3k}}=\frac{\alpha^{3kl}-\beta^{3kl}}{\alpha^{3k}-\beta^{3k}}= \alpha^{3k(l-1)}+\ldots+\beta^{3k(l-1)},$$ and substituting $$\alpha^3=2+\sqrt{5},\beta^3=2-\sqrt{5}$$ and expanding the brackets we see that it is odd. Therefore all $$g_s$$ for $$s\ne 3\cdot 2^m,m=0,1,\ldots$$, are odd. $$g_3=2$$ and if $$s=3\cdot 2^m$$, $$m>0$$, we have $$g_{3\cdot 2^m}g_{2^m}F_{3\cdot 2^{m-1}}=F_{3\cdot 2^m}.$$ Using the formula $$F_{2k}=F_k(F_{k-1}+F_{k+1})$$ for $$k=3\cdot 2^{m-1}$$ we finally conclude that $$g_{3\cdot 2^m}$$ is even.

So your claim is equivalent to the following:

if $$n\geqslant 2$$, then all exponents of the form $$\eta(n,3\cdot 2^m)$$ are equal to 0 if and only if $$n=3\cdot 2^j-1$$ for some $$j=0,1,\ldots$$.

If $$n=3m$$ or $$n=3m+1$$ for $$m\geqslant 1$$, $$k=3\cdot 2^s$$, where $$2^s$$ is the maximal power of 2 which divides $$2m$$. We get from $$(\bullet)$$ that $$\eta(n,k)=[2m/2^s]-2[m/2^s]=1$$.

If $$n=3m+2$$ and $$k=3t$$, we get $$\eta(3m+2,3t)=[(2m+1)/t]-[m/t]-[(m+1)/t]$$. For $$t=1$$ this is always 0, for $$t=2^s$$, $$s>0$$, this is the same as $$[(2m)/t]-[m/t]-[(m+1)/t]$$, and this expression is already studied in the answer to your $$q$$-Catalan question. Namely, it is zero for all positive integer $$s$$ if and only if $$m=2^j-1$$ which means $$n=3\cdot 2^j-1$$.