3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – fleablood May 7 '18 at 21:57
  • $\begingroup$ @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. $\endgroup$ – Gottfried Helms May 8 '18 at 6:15
4
$\begingroup$

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*}

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gottfried Helms May 8 '18 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.