Define $A=(a_n)$ and $B=(b_n)$ as follows: $a_0=1$, $a_1=2$, $b_0=3$, $b_1=4$, and $$a_n=a_1b_{n-1}-a_0b_{n-2} + 2n$$ for $n \geq 2$, where $A$ and $B$ are increasing and every positive integer occurs exactly once in $A$ or $B.$ Can someone prove that $$2n < a(n) - \sqrt{2} n < 3+2n$$ for $n \geq 2$ ?

Evidence: $$A = (1, 2, 9, 12, 15, 18, 21, 26, 28, 33, 35, 40, 42, 47, 49, 54, 56,\dots)$$ $$B = (3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 24, 25, \dots)$$ I've checked that $0.207 < a_n - (2+\sqrt{2})n < 2.914$ for $2 <= n <= 18000.$

This question is similar in form to Limit associated with complementary sequences. There P. Majer proves that $a_n - 4n$ is not bounded, whereas here, the claim is that $a_n - (2+\sqrt{2})n$ is bounded.

  • $\begingroup$ Is $b_n=n+3$?.. $\endgroup$ – Maxim Jan 15 '18 at 21:18
  • 3
    $\begingroup$ I don't undestand what is the rule for $(b_n)$. What is $b_2$, for instance (and why)? $\endgroup$ – Filippo Alberto Edoardo Jan 15 '18 at 22:25
  • 1
    $\begingroup$ Experimental fact: $(a_{n+1}-a_n,b_{n+1}-b_n)$ only takes values $(1,1)$, $(2,1)$, $(3,1)$, $(4,1)$, $(5,1)$, $(7,1)$, $(2,2)$, $(3,2)$ and $(5,2)$. $\endgroup$ – მამუკა ჯიბლაძე Jan 15 '18 at 22:25
  • 3
    $\begingroup$ @FilippoAlbertoEdoardo $b_n$ is the smallest number not occurring among $a_1,...,a_n,b_1,...,b_{n-1}$ $\endgroup$ – მამუკა ჯიბლაძე Jan 15 '18 at 22:26
  • 1
    $\begingroup$ @PietroMajer I guess I haven't added all the details below, but that statement follows by (strong) induction. $\endgroup$ – Gjergji Zaimi Jan 16 '18 at 2:48

An illustration for the answer by Gjergji Zaimi: the mysterious sequence $\epsilon_1,\epsilon_2,...,\epsilon_{5000}$

enter image description here

And here, in response to the comment by André Henriques, is the plot of lengths of gaps between consecutive points in the set $\{\epsilon_k\mid10000<k<20000\}$ rearranged in the increasing order. Some Cantor-set-like structure seems to be present indeed.

enter image description here

  • 6
    $\begingroup$ I see a chaotic dynamical system, whose attractor is a Cantor set. $\endgroup$ – André Henriques Jan 16 '18 at 12:14
  • $\begingroup$ @AndréHenriques I do not quite see how to prove that the set of limit points of $\{\epsilon_k\mid k=1,2,...\}$ is nowhere dense. Maybe what can help is that $\epsilon_{k+1}-\epsilon_k$ only takes four values ($-\sqrt2$, $1-\sqrt2$, $2-\sqrt2$, $3-\sqrt2$) but I do not readily see how to use it $\endgroup$ – მამუკა ჯიბლაძე Jan 17 '18 at 3:54

Let's define two auxiliary sequences $c_n=a_{n+2}-a_{n+1}-2$ and $d_n=b_{n+2}-b_{n+1}$ for $n\geq 1$. One can prove with an induction argument that the sequence $c_n$ takes values in $\{0,1,2,3\}$ and $d_n$ takes values in $\{1,2\}$.

The sequence $c_n$ starts: $1,1,1,1,3,0,\dots$ and $d_n$ starts: $1,1,1,2,1,2,1,\dots$.

We know how to get from $d_n$ to $c_n$ with the relation $c_n=2d_{n-1}-d_{n-2}$. There is also a nice way to build $d_n$ from $c_n$ with a substitution step:

Suppose we have the first $m$ terms of $c_n$. If we perform the substitutions $0\to 2,1\to 21,2\to 211,3\to 2111$ and append $1,1,1$ as a prefix, we will obtain the first $m'=3+m+\sum_{n=1}^m c_n$ terms of $d_n$. Their sum is $\sum_{n=1}^{m'}d_n=3+2m+\sum_{n=1}^m c_n$.

Let's denote $\sum_{n=1}^m c_n=\sqrt{2}m+\epsilon_m$. Since $\sum_{n=1}^m c_n=a_{m+2}-2(m+2)-5$, your conjecture can be rephrased as $$-2.172\approx2\sqrt2-5\le \epsilon_m\le 2\sqrt2-2\approx 0.828$$

I'm writing an argument to show that $\epsilon_m$ is bounded, but I get slightly worse constants. Let $f_1$ be some arbitrary natural number. Define $f_2$ to be the smallest natural number for which $\alpha =4+f_2+\sum_{n=1}^{f_2}c_n-f_1\geq 0$. Notice that $\alpha\le 3$. We can write $$\sum_{n=1}^{f_1}c_n=2d_{f_1-1}+d_{f_1-2}+\cdots+d_1$$ $$\implies \sqrt{2}f_1+\epsilon_{f_1}=d_{f_1-1}+3+2f_2+\sqrt{2}f_2+\epsilon_{f_2}-\alpha$$ and we also have $$f_1=4+f_2+\sqrt{2}f_2+\epsilon_{f_2}-\alpha$$ So, by taking $\sqrt2$ times the second equation minus the first we get $$\epsilon_{f_1}=d_{f_1-1}-1-(\sqrt2-1)(4+\epsilon_{f_2}-\alpha).$$ Since $d_{f_1-1}\in [1,2]$ and $\alpha\in [0,3]$ this gives $$\epsilon_m\in \left[\frac{\sqrt{2}-6}{2},\frac{5\sqrt{2}-4}{2}\right]\approx [-2.293,1.535]$$ for all $m$. (One can check that if $\epsilon_{f_2}$ belongs to this interval then so must $\epsilon_{f_1}$ and use strong induction.)

| cite | improve this answer | |
  • 4
    $\begingroup$ As a consequence, $a_n$ can't satisfy any linear (or polynomial) $r$ terms recurrence, otherwise $c_n$ would also satisfy some finite terms recurrence; but then $c_n$, being also finite-valued, would be (eventually) periodic, and the limit $a_n/n$ would be a rational number! $\endgroup$ – Pietro Majer Jan 16 '18 at 8:20
  • $\begingroup$ Is there a typo? Since $b_n$ takes values in $\{1,2\}$, then $d_n$ take values in $\{-1,0,1\}$, but the substitution you have, that should reproduce $d_n$, in fact gives strings of $1$'s and $2$'s only. $\endgroup$ – Pietro Majer Jan 16 '18 at 23:56
  • $\begingroup$ btw the substitution map from the sequence $a_{n+1}-a_n$ to itself I got was $2\to4$, $3\to25$, $4\to235$, $5\to2335$, with prefix $3333{\bf5}$ (say with country code $17$, which we may forget) $\endgroup$ – Pietro Majer Jan 17 '18 at 0:11
  • 1
    $\begingroup$ Yes, oops, I meant $d_n$ of course. $\endgroup$ – Gjergji Zaimi Jan 17 '18 at 0:12

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.