5
$\begingroup$

It is well known that for each pair $f_n,f_m$ in Fibonacci sequence we have $$\gcd(f_n,f_m)=f_{\gcd(n,m)}$$

What about the other way? If we have $\gcd(a_n,a_m)=a_{\gcd(n,m)}$ for each pair in nonconstant sequence $a_1,a_2,...$ of natural nubers, then it is Fibonacci sequence?

For start I was thinking only about a sequence of form $a_{n+1} = \alpha a_n+ \beta a_{n-1}$ and all I can find is that $a_1=a_2$ and that $a_1\mid a_n$ for each $n$. Also $a_2\mid a_3$.

$\endgroup$
4
8
$\begingroup$

A sequence $(x_n)$ satisfying $\gcd(x_n,x_m)=x_{\gcd(n,m)}$ is called a strong divisibility sequence.

A simple example of a strong divisibility sequence that is not the Fibonacci sequence is $x_n = a^n-1$, where $a \in \mathbb N$.

$\endgroup$
3
  • $\begingroup$ See also math.stackexchange.com/questions/7473/…. $\endgroup$ – lhf Mar 27 '18 at 20:44
  • 1
    $\begingroup$ Also, note that these sequences are of the form specified by OP: since they are a linear combination of two exponentials $r\cdot a^n+s\cdot 1^n$ (where $r=1, s=-1$) then they satisfy a linear recurrence whose characteristic polynomial has roots $a, 1$; in other words, whose characteristic equation is $(x-a)(x-1) = x^2-(a+1)+a=0$, or (pulling it back to the recurrence) $x_n = (a+1)x_{n-1}-ax_{n-2}$ with appropriate initial conditions ($x_0=0, x_1=a-1$). $\endgroup$ – Steven Stadnicki Mar 27 '18 at 21:26
  • 1
    $\begingroup$ Look in the OEIS for interesting examples of elliptic divisibility sequences. $\endgroup$ – Somos Mar 28 '18 at 0:12

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.