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$}.$$

  • $\begingroup$ I think, $FC_1=1$ and $n=1$ is not of this form $\endgroup$ Mar 27, 2019 at 2:18
  • $\begingroup$ That is right, I was meaning to write $n>1$. Thanks. $\endgroup$ Mar 27, 2019 at 3:07
  • $\begingroup$ 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. $\endgroup$ Mar 28, 2019 at 4:19
  • $\begingroup$ @AlexanderBurstein: That's a good question, please look at the above update. $\endgroup$ Mar 28, 2019 at 16:35
  • $\begingroup$ @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) $\endgroup$ Mar 29, 2019 at 3:49

1 Answer 1


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.