Uniqueness of values in recurrence relations Given an integer $k > 1$, define the sequences $X(k,n), Y(k,n)$ as follows:

$a=4k-2,$  $y_0 = 1,$  $y_1 = a + 1,y_n = ay_{n-1} - y_{n-2}$

$b   = 4k + 2,$  $ x_0 = 1,$  $x_1 = b - 1,$  $x_n = bx_{n-1} - x_{n-2}$

For example, with $k = 2$ we get  
$y_j = 7, 41, 239, 1393, \ldots$
$x_j = 9, 89, 881, 8721, \ldots$
A simple question arises, as to whether there exist $\{k, i, j\}$ such that $X(k,i) = Y(k,j)$?
This might well be an open question, and perhaps inappropriate here, but I have trawled the web for many hours and have found no evidence that anybody has even considered it.
Computational experiments suggest that in fact an even stronger result is possible, ie. that there are no $\{k_1, k_2, i>1, j>1\}$ with $X(k_1,i) = Y(k_2,j)$.
In other words, with the exception of $x_1, y_1$ which can be any odd number > 7, all values generated by these sequences appear to be unique.
Any suggestions as to a way to attack this question  would be greatly appreciated!
Update: There are explicit proofs that for $k = 2, 3$ there can be no $X(k,i) = Y(k,j)$, so we can restrict the question to $k > 3$.  Sadly these proofs are not extendable to other k
 A: You may consider the paper:
B. Ibrahimpasic, A parametric family of quartic Thue inequalities. 
Bull. Malays. Math. Sci. Soc. (2) 34 (2011), no. 2, 215–230, 
available at http://www.emis.de/journals/BMMSS/vol34_2_2.html 
It seems that Theorem 3.1, with c=2k, answers your question.
A: Ok, Aaron has generalised my sequences $X(k), Y(k)$ to $U(m), V(m)$ for arbitrary m > 2.

It will be found that any pair $(u, v) = (U_j(m), V_j(m))$ corresponds to a solution to the generalised Pell equation
$(m+2)v^2 - (m-2)u^2 = 4$

If $m = 4k$ then this reduces to $(2k+1)v^2 - 2ku^2 = 2$, and for $m = 4k-2$ we get
$kv^2 - (k-1)u^2 = 1$.

This explains why cases $m = 3, 4, 6$ produce convergents to $\sqrt{5}, \sqrt{3}, \sqrt{2}$ respectively, since they correspond to regular Pell equations:


$m=3: 5v^2 - u^2 = 4$
$m=4: 3v^2 - u^2 = 2$
$m=6: 2v^2 - u^2 = 1$
My original question is thus restated as "Does $U_j(4k-2) = V_i(4k+2)$ have any solutions?".  Which itself can be restated as, are there any solutions to the simultaneous equations:

$kx^2 - (k-1)y^2 = 1$
$(k+1)y^2 - kz^2 = 1$


with k > 1, noting again that cases k = 2, 3 have been resolved in the negative.
And the motivating question is this: do there exist squares in arithmetic progression that can be written $(k-1)n +1, kn+1, (k+1)n+1$, with $n > 0, k > 1$?
If so, they necessarily correspond to solutions $\{x,y,z\}$ of these equations, with $n = (x^2 -1)/(k-1) = (y^2 -1)/k = (z^2-1)/(k+1)$
A: Thanks, Aaron.  Your comment has reminded me that I have been negligent in the
computational searches conducted so far, in that I have failed to report any
information on minimum distances encountered.  I will attend to that.

By the way, I have reversed the definitions of X and Y above as they were the opposite
of what I have in all existing code and research notes. My apologies!

In terms of k the first few polynomials are
$Py_1  = 4k - 1$
$Px_1  = 4k + 1$

$Py_2  = 16k^2 - 12k + 1$
$Px_2  = 16k^2 + 12k + 1$

$Py_3  = 64k^3 -  80k^2 + 24k - 1$
$Px_3  = 64k^3 +  80k^2 + 24k + 1$

$Py_4  = 256k^4 - 448k^3 + 240k^2 - 40k + 1$
$Px_4 = 256k^4 + 448k^3 + 240k^2 + 40k + 1$

If we define the distance polynomial $D_{j,i} = Py_j - Px_i$ then  $D_{2,1} = 16k^2 - 16k$ so the quadratic case is disposed of, as you say.
We can also rule out the cubic case, and in fact all odd j. We have
$D_{3,1} = 64k^3 - 80k^2 + 20k - 2$
$D_{3,2} = 64k^3 - 96k^2 + 12k - 2$
For all odd j we get even coefficients and $c_0 = -2$, so no $D_{2e+1,i}$ can have an integer root $k > 1$.
For even j we get polys like these:
$D_{4,1} = 56k^4 - 448k^3 + 240k^2 - 44k$
$D_{4,2}= 256k^4 - 448k^3 + 224k^2 - 52k$
$D_{4,3} = 256k^4 - 512k^3 + 160k^2 - 64k$
What I'm hoping to find is some magic property for even j that will tell us that all $D_{2e,i}$ are either irreducible or have a single integer root $k=1$.
Since $Y(1,j) = 3,5,7 \ldots$, all of $X(1,i) = 5, 29, 169 \ldots$ are to be found in $Y(1,j)$ so the corresponding $D_{14,2}, D_{84,3} $ etc will all have root $k=1$.
I suspect that all other D are irreducible, but these isolated exceptions are a bit of a fly in the ointment!
Oh yes, and I can tell you that a search on all pairs of sequences $Y(k,j), X(k,i)$ revealed no match for a rather staggering j up to 100,000. For a given depth limit j < J, such a search is finite, since beyond a certain k we find that all $Y(k,J) > X(k,J-1)$ and so we need look no further.
It follows then that the proposition, that all $D_{j,i}$ are either irreducible or have a single integer root $k=1$ is true for all j < 100,000.
A: Aaron prompted me to investigate the behaviour of gaps in the sequences $X(k), Y(k)$, or equivalently $U(m), V(m')$ with $m = 4k-2, m' = 4k+2$, with $k>3$.

I found that, for any k, the distance $D_j$ of any $U_j$ to the nearest $V_i$ is nearly always increasing, with $log_m(D_j) = j - \epsilon$. The only time the distance decreased was at a "sync point", ie a point j where $V_i < U_j < U_{j+1} < V_{i+1}$. The $D_j, D_{j+1}$ values tend to be very close together and sometimes $D_{j+1}$ is marginally less than $D_j$. 

Given this trend, I wonder whether the case for "no coincidences" is strengthened. If coincidences were possible, then wouldn't I expect to see $D_j$ fluctuate?
