Intersection of two recurrences. I have two sequences obtained by recurrences:
$$f(0) = 1, f(1) = 9, f(n+2) = 10f(n+1) - f(n)$$
$$g(0) = 1, g(1) = 7, g(n+2) = 6g(n+1) - g(n)$$
How can I prove that apart from $f(0) = g(0) = 1$, these sequences have no common elements? Or if they do, how can I find them? More formally:

Find all $(m,n)$ for which $f(m) = g(n)$.

All I managed to do is prove that elements of $f(n)$ have form of $20d + 1$ or $20d + 9$.
It also seems that $f(n)$ are solutions to diophantine equation $6n^2 - 2 = a^2$ for $n$ and $g(n)$ are solutions to $\frac{n^2+1}{2} = b^2$.
 A: Jan,
Your question has been studied in much greater generality in the references below:


*

*M. Laurent. Équations exponentielles polynômes et suites récurrentes linéaires. Astérisque 147–148 (1987), 121–139.

*H. P. Schlickewei and W. Schmidt. Linear equations in members of recurrence sequences. Ann. Scuola Norm. Sup. Pisa Cl. Sci. 20 (1993), 219–246.

*H. P. Schlickewei and W. Schmidt. The intersection of recurrence sequences. Acta Arith. 72 (1995), 1–44.


Since the roots of the characteristic equation of $f$ and $g$ are not related, there can only be finite number of solutions.
Please note I have copied from my own answer to a related problem.  Let me know if it is inappropriate to post duplicate information.
A: Hint:
The characteristic equation for the first recurrence is
$$r^2-10r+1=0$$
Its two roots are 
$$r_1=5 + 2\sqrt{6} \quad \text{ and } \quad r_2=5 - 2\sqrt{6}$$ 
Thus the solution to this recurrence will be of the form 
$$f(n)=A\left(5 + 2\sqrt{6}\right)^n+B\left(5 - 2\sqrt{6}\right)^n.$$
Using the initial condition solve for $A$ and $B$. Do the same with $g(n)$ and then you can answer your question.
