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
    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
    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
    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
    Nov 30, 2014 at 1:52
  • $\begingroup$ Well, Jeremy Rouse's neat answer below does vindicate the question! $\endgroup$
    – Yaakov Baruch
    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
    Nov 30, 2014 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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