4
$\begingroup$

Let $F_n=1,1,2,3,5,\ldots$ (starting with $n=1$) be the Fibonacci sequence and let $C_n=\frac{1}{n+1}\binom{2n}{n}$ be the Catalan sequence. Define $B_z$ to be the cardinality of $$B_z := \#\bigl\{ n \leq z | \gcd(F_n,C_n)=1 \bigr\}.$$ It seems $$\lim_{z\to\infty} \frac{B_z}{z}=\frac14.$$ Posted a related question here: https://math.stackexchange.com/questions/2131648/gcd-of-catalan-and-fibonacci-numbers, but it got no answer and, thinking a bit about it, the question might be more research related than elementary (but I have no real training in such questions). So question is: Does $B_z/z$ converge, and if so, to what? Here some values of $g_z := B_z/z$, $$g_{1000}=\frac{71}{250}=0.284, \quad g_{2000}=\frac{13}{50}=0.260, \quad g_{3000}= \frac{187}{750}\approx0.249, \quad g_{4000}=\frac{979}{4000}\approx0.245.$$ The sequence of integers such that the gcd is one starts with $$1,2,3,4,5,8,10,11,13,14,17,22,23,25,\ldots$$ and is probably not known in the sequence database.

$\endgroup$
  • $\begingroup$ Are you assuming $F_0 = F_1 = 1$ or $F_1 = F_2 = 1$? $\endgroup$ – D. Ror. Feb 7 '17 at 18:10
  • $\begingroup$ $F_1=F_2=1$.Long comment needed. $\endgroup$ – Mare Feb 7 '17 at 18:12
  • $\begingroup$ Yes -- in the stackexchange question there was confusion caused by the fact that if you re-index the Fibonacci sequence then this completely changes $B_z$. So perhaps why not list the first few $F_n$ and $C_n$, plus the first few $n$ such that the gcd is 1, so everyone knows we're talking about the same question. $\endgroup$ – Kevin Buzzard Feb 7 '17 at 18:13
  • $\begingroup$ No, I justed needed to add something because $F_1=F_2=1$ was too short for a comment. $\endgroup$ – Mare Feb 7 '17 at 18:14
  • 1
    $\begingroup$ No but honestly, put it into the question, so people can just read the MO question (and not the MO comments, or the SE question, or the SE comments etc) -- you will be more likely to get a response that way. In particular the first few $n$ such that the gcd is 1 will be a very useful thing to have in the question so that people know quickly if they have made a mistake. $\endgroup$ – Kevin Buzzard Feb 7 '17 at 18:17
4
$\begingroup$

This is a bit overlong for a comment, and not really an answer, but includes some information about a related problem that might offer approaches to this one. In particular, the fact that the Fibonacci sequence is a divisibility sequence means that gcd properties involving $F_n$ are tied into properties for $F_m$ for $m\mid n$. So you might try looking at the proportion of primes in your set.

The Fibonacci sequence is a linear recursion and a divisibility sequence. For a similar question in which one takes two Fibonacci-type sequences, there are conjectures, but not even an inkling of a proof. For example, Ailon and Rudnick conjectured that $$\{n\ge1 : \gcd(2^n-1,3^n-1)=1\}$$ is infinite, and I published a somewhat dubious heuristic argument that $$\text{Density}\Bigl(\{p~\text{prime}:\gcd(2^p-1,3^p-1)=1\}\Bigr)=1.$$ (The density over all $n\in\mathbb{N}$ seems harder to guess.) More generally, due to the divisibility property of these sequences, for $a,b\ge2$ multiplicatively independent, it is natural to look at $$\{n\ge1 : \gcd(a^n-1,b^n-1)=\gcd(a-1,b-1)\}.$$ I'll also mention that Ailon and Rudnick proved a stronger version of their conjecture when one replaces the integers $a$ and $b$ with polynomials $a(T),b(T)\in\mathbb{C}[T]$.

$\endgroup$
  • $\begingroup$ There is a good reason that Joe Silverman brought in those gcd problems: for each prime $p$ there is smallest integer $\alpha(p)$ such that $\nu_p(F_{\alpha(p)})=1$. With this number, $\nu_p(F_{n\cdot\alpha(p)})=\nu_p((p+1)^n-1)$ and $\nu_p(F_m)=0$ (whenever $\alpha(p)$ does not divide $m$). Of course, $\nu_p((p+1)^n-1)=\nu_p(pn)$ but that is not my point. The intent is to indicate that $x^n-1$ enters the picture of divisibility of the Fibonacci number. $\endgroup$ – T. Amdeberhan Feb 8 '17 at 4:39

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.