Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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