# 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

-

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

-
Brilliant! Thank you. How on earth did you spot that? – Jim White Jan 10 '13 at 17:38
I was PhD thesis supervisor of the author of that paper :) You can find some similar results in papers by Borka Jadrijevic marjan.fesb.hr/~borka/popis_znanstvenih_radova.htm – duje Jan 10 '13 at 17:45
Thanks again. May I ask, would your first name be Andrej? If so we have a connection. – Jim White Jan 10 '13 at 19:08
yes, my first name is Andrej – duje Jan 10 '13 at 19:13
I co-authored a paper with Keith Matthews on your conjecture wrt $x^2 - (k+1)y^2 = k^2$, which we submitted to you recently. I found the recursive structure of solutions described therein. – Jim White Jan 10 '13 at 19:15

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

-
I've wondered about similar things. I'm interested in finding triples of nearly equal integers integers with square product. That would require (or at least benefit from) hits among near optimal rational approximates to square roots. A pretty impressive example is $(10082,10086,10092)=(2a^2,6b^2,3c^2)$ where $a/b=71/41$ and $b/c=41/29$ are convergents to $\sqrt{3}$ and $\sqrt{2}$. That is enough although that drags along $22/9,49/20$ which are convergents to $\sqrt{6}$ with $(22+49)/(9+20)=a/c.$ – Aaron Meyerowitz Jan 9 '13 at 12:36
Aaron, that sounds like fun, is there anything I can do to contribute? – Jim White Jan 11 '13 at 1:39

I have extended your definitions to have four times as many sequences (sorry to add a third set of definitions). If I am not mistaken there are exactly $11$ interesting repeated entries up to $10^{12}$, none of which affect your restricted case: You might find a few ideas here. This is just meant to reinforce the idea that there is no deep reason that coincidences could not occur, and a few do. But the numbers are so sparse that it seems reasonable that only finitely few do, except some obvious small identities.

Consider the two sequences

$U_n(m)=1, m+1, m^2+m-1, m^3+m^2-2m-1, m^4+m^3-3m^2-2m+1,\cdots$ given by the recurrence $U_{i}=mU_{i-1}-U_{i-2}$ (for $i \ge 2$) with initial conditions $U_0=1,U_1=m+1$

and

$V_n(m)=1, m-1, m^2-m-1, m^3-m^2-2m+1, m^4-m^3-3m^2+2m+1,\cdots$ given by the same recurrence $V_{i}=mV_{i-1}-V_{i-2}$ (for $i \ge 2$) but with initial conditions $V_0=1,V_1=m-1$

Then the $U_i,V_i$ can be expressed as linear combinations of the roots $r=\frac{m \pm \sqrt{m^2-4}}{2}$ of $r^2-r+1=0.$ One of the roots is very close to $\frac{1}{m}$ and the other close to $m-\frac{1}{m}.$ SO, after a bit of computation,

$U_i(m)=\lfloor{\frac{m-2+\sqrt{m^2-4}}{2(m-2)} \left( \frac{m+\sqrt{m^2-4}}{m-2}\right)^n}\rceil$ and

$V_i(m)=\lfloor{\frac{m+2+\sqrt{m^2-4}}{2(m+2)} \left( \frac{m+\sqrt{m^2-4}}{m+2}\right)^n} \rceil$ where $\lfloor z\rceil$ means round to the nearest integer, which in this case will be very close.(The distance from the nearest integer goes to $0$ like $\frac{1}{m^n}$). The approximation will be of the form $U_i(m)=v \approx \frac{v}{2}+\frac{p\sqrt{m^2-4}}{q}$

I don't know that it matters, but we see from this (after more computation) that $\frac{U_i(m)}{V_i(m)}\approx\sqrt{\frac{m+2}{m-2}}$ where the approximation is quite good. For $m=4,6$ we have $\sqrt{\frac{m+2}{m-2}}=\sqrt{3},\sqrt{2}.$ Observe in the tables below that $U(4),V(4)$ give the numerators and denominators of alternate terms of the sequence $1/1,2/1, 5/3, 7/4, 19/11, 26/15, 71/41, 97/56, 265/153, 362/209,\cdots$ of convergents to $\sqrt{3}.$ Similarly, $U(6),V(6)$ give the numerators and denominators of alternate terms of the sequence $1/1,3/2,7/5,17/12,41/29,99/70,239/169,577/408,1393/985,\cdots$ of convergents to $\sqrt{2}.$ Similar things can be observed and explained. I'll only mention that, while the relation to $\sqrt{5}$ at $m=3$ is less obvious (though there) a consequence is that half of the Fibonacci numbers constitute $V(3)$ and another quarter constitute $U(7).$

Here are the first few terms of $U(m)$ then $v(m)$ for $3 \le m \le 17.$ Values over $1000000$ are not shown. As just mentioned, numerators and denominators of convergents to $\sqrt{2}$ show up as $U(6),V(6)$ respectively with growth rate $(1+\sqrt{2})^2=3+2\sqrt{2}=5.828\cdots \approx 6-1/6 \approx 6$ This illustrates that the terms in $U(m)$ and in $V(m)$ grow very much like $m^i$. More precisely, they grow like $(\frac{m+\sqrt{m^2-4}}{2})^n \approx (m-\frac1m)^n.$

$\begin{array}{cccccccccc} 4&11&29&76&199&521&1364&3571&9349& 24476\\\ 5&19&71&265&989&3691&13775&51409&191861& 716035\\\ 6&29&139&666&3191&15289&73254&350981&-&- \\\ 7&41&239&1393&8119&47321&275807&-&-&- \\\ 8&55&377&2584&17711&121393&832040&-&-&- \\\ 9&71&559&4401&34649&272791&-&-&-&- \\\ 10&89&791&7030&62479&555281&-&-&-&- \\\ 11&109&1079&10681&105731&-&-&-&-&- \\\ 12&131&1429&15588&170039&-&-&-&-&- \\\ 13&155&1847&22009&262261&-&-&-&-&- \\\ 14&181&2339&30226&390599&-&-&-&-&- \\\ 15&209&2911&40545&564719&-&-&-&-&- \\\ 16&239&3569&53296&795871&-&-&-&-&-\end{array}$

$\begin{array}{cccccccccc} 2&5&13&34&89&233&610&1597&4181& 10946\\\ 3&11&41&153&571&2131&7953&29681&110771& 413403\\\ 4&19&91&436&2089&10009&47956&229771&-&- \\\ 5&29&169&985&5741&33461&195025&-&-&- \\\ 6&41&281&1926&13201&90481&620166&-&-&- \\\ 7&55&433&3409&26839&211303&-&-&-&- \\\ 8&71&631&5608&49841&442961&-&-&-&- \\\ 9&89&881&8721&86329&854569&-&-&-&- \\\ 10&109&1189&12970&141481&-&-&-&-&- \\\ 11&131&1561&18601&221651&-&-&-&-&- \\\ 12&155&2003&25884&334489&-&-&-&-&- \\\ 13&181&2521&35113&489061&-&-&-&-&- \\\ 14&209&3121&46606&695969&-&-&-&-&- \\\ 15&239&3809&60705&967471&-&-&-&-&- \\\ 16&271&4591&77776&-&-&-&-&-&- \\\ 17&305&5473&98209&-&-&-&-&-&-\end{array}$

You are only using the rows $U(4k-2)$ and $V(4k+2)$ for $k \ge 2.$ Here are some observations on the coincidences if we uses all the rows (none of these coincidences show up for your selection).

The $U_1$ and $V_1$ are all the integers so should not count for coincidences.

$U_2(m)=V_2(m+1)=m^2-m+1$

There are six sporadic cases of $v=U_3(m)=U_2(m').$ Equivalently, $U_3(m)=V_2(m'+1)$. These are for $(v,m,m')=(29,3,5),(71,4,8),(239,6,15),$$(60761,39,246),(2370059,133,1539)(6679639,188,2584).$ There might be more, but I doubt it. This is complete up to $v=25 \cdot 10^{18}.$

Here is an analysis: To solve $m^3+m^2-2m-1=(m')^2+m'-1$ we can use the quadratic formula to solve $m'=\frac{-1+\sqrt{4m^3+4m^2-8m+1}}{2}$ SO the cubic under the radical must be a perfect square. This is a matter of looking for integer points on an elliptic curve for which there is a well developed theory (which I did not use.) One expects finitely many. One could check if the integer points given lead any others using the group law. It might be that this kind of analysis (which I did not really do here anyway) could also be done for some $U_4,V_4,U_6,V_6.$

The other repeats up to $10^{12}$ are $41=V_3(4)=U_2(6),\ 89=V_3(5)=U_2(9),\ 1189=V_3(11)=U_2(34)$ along with $3191=U_5(5)=U_2(56)$ and $13201=V_5(7)=V_3(24).$

Note: to check up to $10^{12}$ we can generate the $U_3(m)$ and $V_3(m)$ up to $m=10^4$ along with any $U_i(m) \lt 10^{12}$ and $V_i(m) \lt 10^{12}$ for $i \gt 3.$ In all this is about $43000$ vaues. We could also generate $U_2(m)=m^2+m-1$ up to $m=10^6$ but $m^2+m-1=v$ for $v=\frac{-1+\sqrt{5+4v}}{2}$ so it is better to just check which of the other values make the expression under the radical a square. However this does make it harder to check for the smallest gaps. It could still be done but I did not.

My feeling is that there are a handful of repeated terms for coincidental reasons and that it is reasonable on random grounds to expect that there are only finitely many. Quite possibly just the $10$ I mentioned. There does not seem to be any underlying meaning for the coincidences. For example

$239=U_3(6) \approx \frac{239+169\sqrt{2}}{2}\approx 239.001046$ and also $239=U_2(15)\approx \frac{239}{2}+\frac{209\sqrt{221}}{26} \approx 239.0003219.$ I do not see anything deep here. However the fact that the rational and irrational parts are nearly equal is not a coincidence.

Other thoughts: In a sense, $U(m)$ and $V(m)$ are just scaled versions of the powers of $m$ so we kind of have the prime powers (twice). We now know for sure that the set of powers $m^i$ (starting at $2^4=16$) and the set of near powers $b^j\pm1$ ($i,j \ge 2$) are disjoint. There are many conjectures about the the growth rate of gaps.Your sets are sparser than these by a factor of two. Even with four times as many entries as you are using, so twice the density of the integer powers, there are few coincidences.

One could consider other sequences given by the same recurrence but with other initial conditions. That would provide the "missing" convergents and Fibonacci numbers. I wondered why you chose exactly the ones you did. Is there an motivating problem? There are also other second order recurrences with only one root larger than $1$ in absolute value. Namely: $W_{i+1}=mW_i+cW_{i-1}$ where $-(m+1) \lt c \lt m-1$.

-
<br><br>I will explain why I'm so interested in $U(4k−2)$' and $V(4k+2)$' in a separate answer below, and yes, there is a motivating problem! – Jim White Jan 9 '13 at 6:10
You've listed 9 coincidences, I found 11. The two others are $41=V_3(4)=U_2(6)$ and $1189=V_3(11)=U_2(34)$. – Jim White Jan 10 '13 at 12:52
I can confirm that these 11 coincidences remain the only ones found for $u, v < 2^80$, so you are probably correct in your conjecture. <br><br> If that is the case then we have identified all solutions to the simultaneous equations:<br> <blockquote>$(m+2)v^2 - (m-2)u^2 = 4$<br> $mv^2 - (m-4)u^2 = 4$ </blockquote> and perhaps a couple of other forms. <br><br> It is also fascinating that 10 of the 11 coincidences involve $U_2, V_2$. The case $13201 = V_5(7) = V_3(24)$ is unique in that respect. – Jim White Jan 10 '13 at 19:40
Sorry, still getting to grips with what you can and can't do in a comment! :) Like no html tags, and no editing: I meant to say $u,v < 2^{80}$ – Jim White Jan 10 '13 at 19:43
And the second equation should of course read $mz^2 - (m-4)u^2 = 4$. For example, from $29 = U_2(5) = V_2(6)$ we obtain $7v^2 - 3u^2 = 5z^2 - u^2 = 4$ with $z=13, v=19, u=29$. – Jim White Jan 10 '13 at 19:59

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.

-

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?

-
Dr. Memory, I believe you have enough "reputation" (points) now to be leaving comments under answers, rather than creating more "answers" just to make comments. – Todd Trimble Jan 10 '13 at 14:04
My apologies! I wasn't trying to rack up points but was concerned about the apparent size limit on comments. Eg: my discussion of the polynomials in the answer immediately above, would surely not fit? – Jim White Jan 10 '13 at 17:20
Another problem is that you don't seem to be able to edit comments – Jim White Jan 10 '13 at 19:49
No worries at all, and I wasn't implying you were doing this to rack up points; I just didn't know if you were aware. It's fine to fill up more than one comment box if you need to. And yes, it is impossible to edit comments, which is indeed annoying (but that will change once we make the move to MO 2.0); one is probably better off writing a comment in a text editor and then pasting it in, although I admit I never bother doing this myself. Finally, I should have said before: welcome to MO! :-) – Todd Trimble Jan 10 '13 at 21:51
Thanks Todd! I'm very happy to be here :) – Jim White Jan 11 '13 at 1:36