Limit associated with complementary sequences

Let $\alpha_*$, $\alpha^*$ denote the lower, respectively upper asymptotic density of the set $A$, and $\beta_*$, $\beta^*$ the lower and upper asymptotic density of the set $B$. Note that $$\limsup_{n\to\infty} {a(n)\over n}=1/\alpha_*\ ,\qquad\liminf_{n\to\infty} {a(n)\over n}=1/\alpha^*$$ $$\limsup_{n\to\infty} {b(n)\over n}=1/\beta_*\ ,\qquad\liminf_{n\to\infty} {b(n)\over n}=1/\beta^*\ .$$ Because $B$ is the complement of $A$ we have $$\alpha_*+\beta^*=\alpha^*+\beta_*=1\ .$$ Also, by the recursive relation $$3 \liminf_{n\to\infty}{b(n)\over n}\le \liminf_{n\to\infty}{a(n)\over n}\le\limsup_{n\to\infty}{a(n)\over n}\le 3 \limsup_{n\to\infty} {b(n)\over n}\ .$$ Gathering together these inequalities one finds $$3\alpha^*+\alpha_*\le 1 \le 3\alpha_*+\alpha^*\ .$$ whence $$\alpha_*=\alpha^*=1/4\ ,$$ as we wished to prove.

[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$.