# Common terms in general Fibonacci sequences

Mathworld notes that "The Fibonacci and Lucas numbers have no common terms except 1 and 3," where the Fibonacci and Lucas numbers are defined by the recurrence relation $a_n=a_{n-1}+a_{n-2}$. For Fibonacci numbers, $a_1=a_2=1$; for Lucas numbers, $a_1=1$, $a_2=3$. How do you prove mathworld's statement?

-
Furthermore, lets put some restrictions on a[1] and a[2]. Let GCD(a[1],a[2])==1 and a[1]<a[2]. Doing some minor computation, I noticed that despite the initial values (a[1], a[2]), sequences with different initial values also share at most 2 terms in common (if the sequences being compared are not just the same sequence started at different indices). How can this be explained? –  Paul Liu Mar 19 '11 at 20:50

Let $f_{n}$ and $l_{n}$ be the Fibonacci and Lucas numbers, we want to show that $f_n \ne l_m$ except for the frivial exceptions ($n=m=1$, $n=2, m=1$ and $n=4, m=2$). To see it you can consider the two sequences $f_{n+k}$ and $l_{n}$ slinding one with the other $k$ positions. The only exceptions arise in the first few values of $k$:

              k=0         k=1          k=2
f_{n+k}    1 1 2 3 5    1 2 3 5  8    2 3 5 8 13
l_{n}      1 3 4 7 11   1 3 4 7 11    1 3 4 7 11


To see that in this sucessions there are no more coincidences observe that for $k=0$, putting $g_{n} = l_{1+n} - f_{1+n}$ then $g_{1} > 1, g_{2} > 1$ and $g_{n}=g_{n-1}+g_{n-2}$ so $g_{n} > f_{n}$ for all $n$ and $f_{1+n} \ne l_{1+n}$ for all $n$.

You can do exactly the same for $k = 1$ since $g_{n} = l_{1+n}-f_{2+n}$ and for $k=2$ putting $g_{n} = f_{4+n}-l_{2+n}$, and again in both cases $g_{1} \ge 1$ and $g_{2} \ge 1$ so $g_{n} \ge f_{n}> 0$, and in consequence $f_{n+2}\ne l_{n+1}$ and $f_{n+4}\ne l_{n+2}$ for $n \ge 1$.

Finally to see that for $k>2$ there are no more exception the argument is the same put $g_{n} = f_{n+k}-l_{n}$ we have $g_{1} \ge f_{4} - 1 \ge 1$ and $g_{2} \ge f_{5}-3 \ge 1$ and $g_{n}=g_{n-1}+g_{n-2}$ so $g_{n} \ge f_{n}>0$. The case $k< 0$ is identical using instead the function $g_{n} = l_{n-k} - f_{n}$.

-
Thank you very much. I can definitely apply this reasoning to linear recurrence sequences of the same type! :) –  Paul Liu Mar 20 '11 at 23:05