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

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.

• Is $b_n=n+3$?.. – Maxim Jan 15 '18 at 21:18
• I don't undestand what is the rule for $(b_n)$. What is $b_2$, for instance (and why)? – Filippo Alberto Edoardo Jan 15 '18 at 22:25
• 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)$. – მამუკა ჯიბლაძე Jan 15 '18 at 22:25
• @FilippoAlbertoEdoardo $b_n$ is the smallest number not occurring among $a_1,...,a_n,b_1,...,b_{n-1}$ – მამუკა ჯიბლაძე Jan 15 '18 at 22:26
• @PietroMajer I guess I haven't added all the details below, but that statement follows by (strong) induction. – 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}$

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.

• I see a chaotic dynamical system, whose attractor is a Cantor set. – André Henriques Jan 16 '18 at 12:14
• @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 – მამუკა ჯიბლაძე 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.)

• 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! – Pietro Majer Jan 16 '18 at 8:20
• 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. – Pietro Majer Jan 16 '18 at 23:56
• 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) – Pietro Majer Jan 17 '18 at 0:11
• Yes, oops, I meant $d_n$ of course. – Gjergji Zaimi Jan 17 '18 at 0:12