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
    Commented Jan 15, 2018 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$ Commented Jan 15, 2018 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$ Commented Jan 15, 2018 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$ Commented Jan 15, 2018 at 22:26
  • 1
    $\begingroup$ @PietroMajer I guess I haven't added all the details below, but that statement follows by (strong) induction. $\endgroup$ Commented Jan 16, 2018 at 2:48

2 Answers 2


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$ Commented Jan 16, 2018 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$ Commented Jan 17, 2018 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.)

  • 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$ Commented Jan 16, 2018 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$ Commented Jan 16, 2018 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$ Commented Jan 17, 2018 at 0:11
  • 1
    $\begingroup$ Yes, oops, I meant $d_n$ of course. $\endgroup$ Commented Jan 17, 2018 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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