14
$\begingroup$

The $n=3$'rd Catalan number (A000108) is $1,1,2,5$ : $\frac{\binom{2n}{n}}{n+1}=\frac{\binom{6}{3}}{4}=\frac{20}{4}=$ 5.

The $n=4$'th Fibonacci number (A000045) is $1,1,2,3,5,...$ : 5.

Q. Which other Fibonacci numbers (besides $\{1,2,5\}$) are also Catalan numbers?

There seems to be no other "small" solutions, at least up to Fibonacci/Catalan numbers around $10^{60}$.

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ the $n$th Catalan number is about $4^n$, and the $n$th Fibonacci number is about $\phi^n$. So a coincidence between Catalan and Fibonacci numbers would give a very good rational approximation to $\log 4/\log \phi$. $\endgroup$
    – Will Sawin
    Commented Nov 30, 2014 at 0:37
  • $\begingroup$ @Will: I don't think that a coincidence of Catalan and Fibonacci numbers would give a better rational approximation to $\log 4/\log\phi$ than occurs `in nature'. You know you can find $m$ and $n$ such that $|m\log 4-n\log\phi|<C/m$ by a pigeonhole argument. Since the $m$th Catalan number is about $4^m/(m+1)$, a coincidence would give $|m\log 4-n\log\phi|\lesssim\log m$. $\endgroup$
    – Anthony Quas
    Commented Nov 30, 2014 at 1:26
  • 5
    $\begingroup$ Any reason why the overlap of these two sequences, among many others, would be either useful to know or easy/interesting to compute/prove? $\endgroup$
    – Yaakov Baruch
    Commented Nov 30, 2014 at 1:29
  • $\begingroup$ @YaakovBaruch: Essentially, No. It just so happened that I was employing both sequences within the same hour (there is some similarity to their recursive definitions), and then I wondered if they shared elements beyond $5$. Then it did not seem a trivial question to answer... $\endgroup$
    – Joseph O'Rourke
    Commented Nov 30, 2014 at 1:52
  • $\begingroup$ Well, Jeremy Rouse's neat answer below does vindicate the question! $\endgroup$
    – Yaakov Baruch
    Commented Nov 30, 2014 at 1:59

1 Answer 1

Reset to default
38
$\begingroup$

A result of the type you seek follows easily from Carmichael's theorem, that if $m > 12$, then there is a prime $p$ that divides $F_{m}$, but does not divide $F_{k}$ for $k < m$.

Suppose $C_{n} = \binom{2n}{n}/(n+1)$ and we assume that $C_{n} = F_{m}$. All the prime factors of the left hand side are $\leq 2n$, while by Carmichael's theorem there is a prime $p | F_{m}$ that does not divide any earlier Fibonacci number. However, since for $p > 5$, $p$ divides either $F_{p-1}$ or $F_{p+1}$ we have that $m \leq p+1 \leq 2n$. However, from the asymptotic size of $C_{n}$ and $F_{m}$, we must have that $m \approx \frac{\log(4)}{\log(\phi)} n$, and this contradicts the inequality $m \leq 2n$.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ $\log(4)/\log(\phi) \approx 2.88$. $\endgroup$
    – Joseph O'Rourke
    Commented Nov 30, 2014 at 2:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .