A possibly surprising appearance of $\sqrt{2}.$

Question

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.

Answer 1

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

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.

Answer 2

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