Common terms in general Fibonacci sequences

Question

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?

Answer 1

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}$.