Intersection of two recurrences.

Question

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

Answer 1

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.

Answer 2

Jan,

Your question has been studied in much greater generality in the references below:

1. M. Laurent. Équations exponentielles polynômes et suites récurrentes linéaires. Astérisque 147–148 (1987), 121–139.
2. H. P. Schlickewei and W. Schmidt. Linear equations in members of recurrence sequences. Ann. Scuola Norm. Sup. Pisa Cl. Sci. 20 (1993), 219–246.
3. 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.