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\_0b\_{n-1}+a\_1b\_{n-2}$$ 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 $\lim\_{n \to \infty} a\_n/n = 4$? 


Here are first terms and some evidence regarding the limit:
$$A = (1,2,10,13,16,19,22,25,29,34,38,43,47,52, \dots)$$
$$B = (3,4,5,6,7,8,9,11,12,14,15,17,18,20,21,23, \dots)$$
I've checked that $-9<a\_n-4n<9$ for $n=1,\dots,10^6$. 



Limit associated with complementary sequences
*[edit 12/01/2018: a remark]*.


The sequence $a\_n-4n$ being unbounded also rules out any polynomial recurrence of the form
$$a\_{n+r+1}=P(a\_{n+1},\dots,a\_{n+r})$$
for $P\in\mathbb{C}[x\_1,\dots,x\_{r}]$.


Otherwise $b\_n:=a\_{n+1}- a\_{n}$ would also satisfy a polynomial recurrence
$$ b\_{n+s+1}=Q(b\_{n+1},\dots,b\_{n+s}),$$
and since we know that $b\_n\in\{3,4,5\}$ for all $n\ge2$, $b\_n$ would be eventually periodic.
But then $a\_n$ would be $cn+O(1)$, (thus with $c=4$, since we do have $a\_n=4n+o(n)$), a contradiction.


*[edit 11/01/2018, to make somehow more concrete statements]*.


To answer the last question: looking more closely at this sequence, it turns out that the sequence $h\_n:=a\_n-4n$ is unbounded, both from above and from below. 
In fact, along the integer sequence
$$n\_k:={261\cdot9^{k}-8k+27\over 32}$$
one has 
$$a\_{n\_k}={261\cdot9^{k}+11\over8}\ ,\qquad a\_{n\_k}-4n\_k= k-2$$
and similarly along the integer sequence
$$m\_k:={231\cdot9^k+8k+25\over32}$$ 
one has
$$a\_{m\_k}={231\cdot9^{k}+1\over8}\ ,\qquad a\_{m\_k}-4m\_k= -k-3$$


So for instance $a\_{3836342}-4\cdot 3836342=-9$ and $a\_{255951767434}-4\cdot255951767434=9$. 


We start with the observation that $\Delta b\_n:=b\_{n+1}-b\_n\ge1$, because $b\_n$ is strictly increasing; so for the finite difference $\Delta a\_n:=a\_{n+1}-a\_n$ we have $$\Delta a\_n=\Delta b\_{n-1}+2\Delta b\_{n-2}\ge3\quad(\text{for } n\ge2).$$ Therefore, apart from the pair $(a\_0,a\_1)$, between any two consecutive elements of $A$ we find at least two consecutive integers, which are elements of $B$. That is, no hole of $B$ is larger than $1$. Thus $\Delta b\_n\in\{0,1\}$ for all $n$, and for the same recurrence above, the values of the sequence $\Delta a\_n$ for $n\ge2$ are taken among the numbers $3,4,$ and $5$ only.


To see better the distribution of these three admissible values, we need to focus on the pairs of consecutive integers $(a\_m,b\_n)\in A\times B$, and distinguish three cases according to the values of $\Delta a\_m$.


If $\Delta a\_m=3$, which means $$b\_{n-2},\ b\_{n-1},\ a\_m,\ b\_n,\ b\_{n+1},\ a\_{m+1}$$ are consecutive integers, we get $$\Delta a\_n=\Delta b\_{n-1}+2\Delta b\_{n-2}=4\ ,\qquad \Delta a\_{n+1}=\Delta b\_{n} +2\Delta b\_{n-1} =5$$ while $(a\_{m+1},b\_{n+2})$ is again a pair of consecutive integers, so that $\Delta a\_{n+3}$ depends on $\Delta a\_{m+1}$ analogously. Similarly, if $\Delta a\_m=4$,
that is $$b\_{n-2},\ b\_{n-1},\ a\_m,\ b\_n,\ b\_{n+1},\ b\_{n+2},\ a\_{m+1}$$ are consecutive integers, then $$\Delta a\_{n}=4\ ,\qquad\Delta a\_{n+1}=5\ ,\qquad\Delta a\_{n+2}=3,$$ while $\Delta a\_{n+3}$ depends on $\Delta a\_{m+1}\ .$
Finally, if $\Delta a\_m=5$ then $$\Delta a\_{n}=4\ ,\qquad\Delta a\_{n+1}=5\ ,\qquad\Delta a\_{n+2}=3,\qquad\Delta a\_{n+3}=3\ ,$$
while $\Delta a\_{n+4}$ depends on $\Delta a\_{m+1}$.


This way the sequence $(\Delta a\_n)\_{n\ge2}$ is completely determined by the initial data $(\Delta a\_n)\_{2\le n\le 6}=(3,3,3,3,3)$: by the above rules, the latter produce the subsequent ten terms $4,5,4,5,4,5,4,5,4,5$; these produce thirty five further terms $4,5,3,4,5,3,3$ and so on. 


To introduce the suitable formalism to describe the situation and make computations more clearly, let $\mathcal{A}$ be the set of symbols $\{\rm a,b,c\}$ and $\mathcal{A}^\*$ the free monoid on $\mathcal{A}$ (In this direction a reference is Richard Stanley's *Enumerative Combinatorics*, vol I, especially the chapter on Rational Generating Functions). Let $\tau:\mathcal{A}^\*\to\mathcal{A}^\*$ the monoid homomorphism defined on generators by $$\tau({\rm a}):={\rm bc}\ ,\qquad\tau({\rm b}):={\rm bca}\ ,\qquad\tau({ \rm c}):={ \rm bcaa}\ .$$ Note that $\tau$ extends to a map, still denoted $\tau$, on the set of infinite strings, $\tau:\mathcal{A}^\mathbb{N}\to\mathcal{A}^\mathbb{N}$, via the left-action of $\mathcal{A}^\*$, that is just $\tau({\bf x})=\tau({\rm x\_0)\tau(x\_1)\tau(x\_2)\tau(x\_3})\cdots$, for any ${\bf x}={\rm x\_0x\_1x\_2x\_3}\cdots\in\mathcal{A}^\mathbb{N}.$ Let ${\bf u}\in\mathcal{A}^\mathbb{N}$ be the unique fixed point of the map ${\bf x}\mapsto {\rm a}^5\tau({\bf x})$, that is
$${\bf u}={\rm a}^5\tau({\bf u})={\rm a}^5\tau({\rm a}^5)\tau^2({\rm a}^5)\tau^3({\rm a}^5)\tau^4({\rm a}^5)\dots=$$
$$={\rm a}^5({\rm bc})^5 ({\rm bcabcaa })^5 ({\rm bcabcaabcbcabcaabcbc})^5 \dots=$$
 $$={\rm aaaaa bcbcbcbcbc bcabcaa bcabcaa bcabcaa bcabcaa bcabcaa bcabcaabcbcabcaabcbc}\cdots$$
(*Warning*: $\tau^3$ e.g. here means the third compositional iterate of $\tau$ that is $\tau\circ\tau\circ\tau$, while ${\rm a}^5$ refers to concatenation: ${\rm aaaaa}$; of course $\tau^3({\rm a}^5)=(\tau^3({\rm a}))^5$.) By the above definition of $\tau$, the string ${\bf u}$, putting $ {\rm a}=3, {\rm b}=4, {\rm c}=5$, produces exactly the sequence of differences $(\Delta a\_n)\_{n\ge2}$. 


Since we are interested in the finite differences of the sequence $h\_n:=a\_n-4n$, we may consider the additive weight function $w:\mathcal{A}^\*\to(\mathbb{Z},+)$ defined on the generators by $w({\rm a})=-1$, $w({\rm b})=0$, $w({\rm c})=1$. So for any ${\rm f}\in \mathcal{A}^\*$ one has $w(\tau({\rm f}))=-w({\rm f})$. Moreover, for any left factor ${\rm f}\in\mathcal{A}^\*$ of ${\bf u}$ of length $\ell({\rm f })=n$, one has $w({\rm f })=h\_{n+2}-h\_{2}$. 


I'll define inductively a sequence ${\rm f}\_k\in\mathcal{A}^\*$ with ${\bf u}={\rm f}\_k{\rm c}\cdots$, and with $w({\rm f}\_k)=-k-5$, which proves that $\Delta h\_n$ is unbounded from below. Indeed we can take ${\rm f}\_0={\rm aaaaab}$; given ${\rm f}\_k$ such that $w({\rm f}\_k)=-k-5$ and ${\bf u}={\rm f}\_k{\rm c}\cdots$, we have by the fixed point equation, 


$${\bf u}={\rm a}^5({\rm bc})^5\tau^2({\rm f}\_k){\rm bcaabc}\cdots$$
whence ${\rm f}\_{k+1}:={\rm a}^5({\rm bc})^5\tau^2({\rm f}\_k){\rm bcaab}$ satisfies both ${\bf u}={\rm f}\_{k+1}{\rm c}\cdots$ and 
$$w({\rm f}\_{k+1})=w\big({\rm a}^5({\rm bc})^5\tau^2({\rm f}\_k){\rm bcaab}\big)=w({\rm f}\_k)+w({\rm bcaab})=-k-6\ .$$


Also, the sequence of left factors ${\rm g}\_k:={\rm a}^5\tau({\rm f\_k})$ satisfies
$$w({\rm g}\_{k})=w({\rm a}^5 \tau ({\rm f}\_k)) =-5+k\ $$
so that we conclude that $h\_n$ is also unbounded from above.


In fact, one can write a linear recurrence for the number of occurrences $x\_k,y\_k$ resp., $z\_k$ of ${\rm a,b,c}$ in ${\rm f}\_k$, yielding to the sequence $m\_k$ mentioned initially, and similarly for a sequence $n\_k$. 


