# Are the sets $\mathbb X=\{0,1,4,15,56,…,x_h,…\}$ and $\mathbb Y=\{0,2,12,70,408,…,y_i,…\}$ (excepting the elements $x_0=y_0=0$) disjunct?

In trying to answer another question I came to the problem as written in the title:

Q1: Are the sets $\mathbb X=\{0,1,4,15,56,...,x_h,...\}$ and $\mathbb Y=\{0,2,12,70,408,...,y_i,...\}$ (excepting the elements $x_0=y_0=0$) disjunct?

and how to approach a proof.

I have two ways to describe the sets as sequences with their elements depending on their indexes: $$x_0=0, x_1=1, x_{h+1}=4x_h-1x_{h-1}\\ y_0=0, y_1=2, y_{i+1}=6y_i-1y_{i-1}\\ \tag 1$$ and using $p=2+\sqrt3$ and $q=3+\sqrt8$ $$x_h = f(h)= \sinh (h \cdot \ln p)/\sqrt 3 \\ y_i =g(i) = \sinh (i \cdot \ln q)/\sqrt 8 \tag 2$$ (The latter is a compacted version of a Binet-like formula (as it is known for instance for the Fibonacci numbers))

What I've tried was ("ansatz 1") to look at the composition of $i=g°^{-1}(f(h))$ and see, whether I can prove, that $i$ is never integer when $h$ is integer, but looking at heuristics and working with the results a bit I do not see any further forcing and/or reliable way to proceed.

Next ("ansatz 2") I've looked at the prime-factorizations of $f(h)$ and $g(i)$ in terms of $h$ resp. $i$. This gives at least insight to some basic facts, for instance that $h$ must be even, then divisible by $3$ and from this $i$ must be divisible by $3$ and so on, and at least leading to a proof for small $h$ and $i$. But this is so far only reasoning for finitely many classes of cases.

Q2: Can my ansatz 1 or ansatz 2 be improved? Or not?
Q3: Is there any differnt route to approach this?

• I propose anyone who says "the set $\{0, 1,4,15, 56...\}$ and the set $\{0,2,12,70, 408,...\}$" and expects it to be understood by hung by their entrails. Anyway the answer is, no, they are not distinct; the 37th element of $X$ and then 408th element of $Y$ are both "Barbar the Elephant in a green Tutu". That's the only element they both have in common. – fleablood May 7 '18 at 21:57
• @fleablood - if you have tried it numerically, I think your software made a truncation error. The second sequence ($y$) has a larger quotient than the first sequence, so it is impossible, that a number in $Y$ with an index larger than an index in $X$ can be equal. – Gottfried Helms May 8 '18 at 6:15

Here is a positive answer to question Q1, and by the way to the question:

Let $k$ be a postive integer number. Then $2k^2+1$ and $3k^2+1$ cannot both be square numbers.

Define the sequences $(x_n),(y_n),(z_n),(r_n),(s_n),(t_n)$ by the following second order linear recurrences: \begin{align*} &x_0=0,\ x_1=1 &x_{n+1}=4x_n-x_{n-1}\\ &y_0=0,\ y_1=2 &y_{n+1}=6y_n-y_{n-1}\\ &z_0=0, \ z_1=1 &z_{n+1}=6z_n-z_{n-1}\\ &r_0=1, \ r_1=2 &r_{n+1}=4r_n-r_{n-1}\\ &s_0=1, \ s_1=5 &s_{n+1}=4s_n-s_{n-1}\\ &t_0=1, \ t_1=3 &t_{n+1}=4t_n-t_{n-1} \end{align*}

It is clear that all the above sequences are monotonically increasing sequences of natural numbers. Also it is clear that $y_n=2z_n$. Now we have the following factorization:

\begin{align*} &x_{2n}=2r_nx_{n} \end{align*}

For the proof for the above factorization, we first show that: \begin{align} \tag{1}\label{1}s_{q+k}+t_{q+k}&=t_ks_q+s_kt_q \\ \tag{2}\label{2}2x_{k+1}&=s_k+t_k\\ \tag{3}\label{3}r_{k}&=\frac{1}{2}(t_k+t_{k-1})\\ \tag{4}\label{4}3x_k&=\frac{1}{2}(s_k+s_{k-1})\\ \tag{5}\label{5}r_{k}&=\frac{1}{2}(s_k-s_{k-1})\\ \tag{6}\label{6}x_{k}&=\frac{1}{2}(t_k-t_{k-1}) \end{align} It is clear that the rhs and lhs in the above relationships are also integer sequences, say $X_k$, satisfying the second order linear recurrence $X_{k+1}=4X_k-X_{k-1}$. Then for proving lhs=rhs, it suffices that they coincide at the index $0$ and the index $1$, which is an easy check. (For $\eqref{1}$, the two indices $k$ and $q$ are treated separately and consecutively). Then multiply equations $\eqref{3}$ and $\eqref{4}$, then multiply $\eqref{5}$ and $\eqref{6}$, then make the difference, reduce and account for $\eqref{1}$ with $q=k-1$ and finally make use of $\eqref{2}$.

If there exist non-zero natural numbers $m,m'$ such that $y_m=x_{m'}$, then $2z_m=x_{m'}$, then $x_{m'}$ is even, then ${m'}$ is even, say ${m'}=2n$. Then, answering yes to question Q1 is equivalent to disprove that there exist non-zero $n,m$ such that $$z_m = r_n x_n$$ We then show that there is no such $m$, because $z_m$ is a monotonically increasing function of $m$ and because we have:

Proposition: For $j>0$, we have: $\ \ \ \ z_{3j-2} < r_{2j-1} x_{2j-1} < z_{3j-1}< r_{2j} x_{2j} < z_{3j}$

We will use the following:

Lemma: For $j>3$, we have: $197z_{j-3}<z_{j}\le204z_{j-3}$.

Proof of the Lemma. \begin{align*} z_{j}=6z_{j-1}-z_{j-2}=35z_{j-2}-6z_{j-3}&=204z_{j-3}-35z_{j-4} \le 204z_{j-3}\\ &=197z_{j-3}+7z_{j-3}-35z_{j-4}\\ &=197z_{j-3}+(42-35)z_{j-4}-7z_{j-5}\\ &=197z_{j-3}+7(z_{j-4}-z_{j-5})\\ &>197z_{j-3} \end{align*} since $z_m$ is a positive and monotonically increasing function of $m$.

Proof of the Proposition.

We show $r_{2j} x_{2j} < z_{3j}$ by induction on $j$. It is true for $j=1$, since $r_{2} x_{2}=28 < 35 = z_{3}$. Suppose (induction hypothesis) that $r_{2(j-1)} x_{2(j-1)} < z_{3j-3}$, for some $j>1$. \begin{align*} r_{2j}&=4r_{2j-1}-r_{2j-2}=16r_{2j-2}-4r_{2j-3}-r_{2j-2}=15r_{2j-2}-4r_{2j-3}\\ x_{2j}&=4x_{2j-1}-x_{2j-2}=16x_{2j-2}-4x_{2j-3}-x_{2j-2}=15x_{2j-2}-4x_{2j-3} \end{align*} But $4r_{2j-3}=r_{2j-2}+r_{2j-4}$ and $4x_{2j-3}=x_{2j-2}+x_{2j-4}$, then \begin{align*} r_{2j}&=14r_{2j-2}-r_{2j-4}<14r_{2j-2}\\ x_{2j}&=14x_{2j-2}-x_{2j-4}<14x_{2j-2} \end{align*} then \begin{align*} r_{2j}x_{2j}&<196r_{2j-2}x_{2j-2}\\ &<196z_{3j-3} \text{ by the induction hypothesis.}\\ & < z_{3j} \text{ by the Lemma.} \end{align*}

We similarly show $r_{2j} x_{2j} > z_{3j-1}$ by induction on $j$. It is true for $j=1$, since $r_{2} x_{2}=28 > 6 = z_{2}$. Suppose (induction hypothesis) that $r_{2(j-1)} x_{2(j-1)} > z_{3j-4}$, for some $j>1$. \begin{align*} r_{2j}&=15r_{2j-2}-4r_{2j-3}=19r_{2j-2}+4(r_{2j-2}-r_{2j-3})>19r_{2j-2}\\ x_{2j}&=15x_{2j-2}-4x_{2j-3}=19x_{2j-2}+4(x_{2j-2}-x_{2j-3})>19x_{2j-2} \end{align*} then \begin{align*} r_{2j}x_{2j}&>361r_{2j-2}x_{2j-2}\\ &>361z_{3j-4} \text{ by the induction hypothesis.}\\ & > z_{3j-1} \text{ by the Lemma.} \end{align*}

We similarly show $r_{2j-1} x_{2j-1} < z_{3j-1}$ by induction on $j$. It is true for $j=1$, since $r_{1} x_{1}=2 < 6 = z_{2}$. Suppose (induction hypothesis) that $r_{2j-3} x_{2j-3} < z_{3j-4}$, for some $j>1$. \begin{align*} r_{2j-1}&=4r_{2j-2}-r_{2j-3}=16r_{2j-3}-4r_{2j-4}-r_{2j-3}=15r_{2j-3}-4r_{2j-4}\\ x_{2j-1}&=4x_{2j-2}-x_{2j-3}=16x_{2j-3}-4x_{2j-4}-x_{2j-3}=15x_{2j-3}-4x_{2j-4} \end{align*} But $4r_{2j-4}=r_{2j-3}+r_{2j-5}$ and $4x_{2j-4}=x_{2j-3}+x_{2j-5}$, then \begin{align*} r_{2j-1}&=14r_{2j-3}-r_{2j-5}<14r_{2j-3}\\ x_{2j-1}&=14x_{2j-3}-x_{2j-5}<14x_{2j-3} \end{align*} then \begin{align*} r_{2j-1}x_{2j-1}&<196r_{2j-3}x_{2j-3}\\ &<196z_{3j-4} \text{ by the induction hypothesis.}\\ & < z_{3j-1} \text{ by the Lemma.} \end{align*}

We similarly show $r_{2j-1} x_{2j-1} > z_{3j-2}$ by induction on $j$. It is true for $j=1$, since $r_{1} x_{1}=2 > 1 = z_{1}$. Suppose (induction hypothesis) that $r_{2j-3)} x_{2j-3} > z_{3j-5}$, for some $j>1$. \begin{align*} r_{2j-1}&=15r_{2j-3}-4r_{2j-4}=19r_{2j-3}+4(r_{2j-3}-r_{2j-4})>19r_{2j-3}\\ x_{2j-1}&=15x_{2j-3}-4x_{2j-4}=19x_{2j-3}+4(x_{2j-3}-x_{2j-4})>19x_{2j-3} \end{align*} then \begin{align*} r_{2j-1}x_{2j-1}&>361r_{2j-3}x_{2j-3}\\ &>361z_{3j-5} \text{ by the induction hypothesis.}\\ & > z_{3j-2} \text{ by the Lemma.} \end{align*}

• Thank you, René! The idea of taking some more sequences into the boat might be a more generally useful trick, I'll see... I can come back to this only later and shall then look what this gives me. (+1) for the effort so far anyway. – Gottfried Helms May 8 '18 at 6:18