Skip to main content
4 of 11
m
Pietro Majer
  • 60.5k
  • 4
  • 122
  • 269

Looking more closely at this sequence, it turns out that the sequence $h_n:=a_n-4n$ is not bounded, both from above and from below. In fact, along suitable integer sequences $n_k$ and $m_k$ (in fact, satisfying linear recurrences) there holds $$h_{n_k}=k\ ,\qquad h_{m_k}=-k\ .$$

I'll recall some algebraic language, that may be of use to study further properties of this sequence or other similar ones.

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 look at the sets $A$ and $B$, how they are interlaced locally at $b_n$, or in other words, where is located the maximum element $a_m$ of $A$ smaller than $b_n$ w.r.to the elements of $B$ nearby.

So 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}$ is the maximum element of $A$ smaller than $b_{n+2}$, 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}$.

For the moment we don't want to bother to make the correspondence $n\mapsto m$ explicit; we may rather use a convenient algebraic formalism and see concisely the sequence $(\Delta a_n)_{n\ge2}$ as an infinite string, that we build concatenating recursively new terms induced by the preceding ones. To describe it more precisely, let $\mathcal{A}$ be the set of symbols $\{\rm a,b,c\}$ and $\mathcal{A}^*$ the free monoid on $\mathcal{A}$. 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})\dots$, for any ${\bf x}={\rm x_0x_1x_2x_3}\dots\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}\dots$$ (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}$. (Double-check: this way, while editing, by means of paste, copy, find, replace, I quickly got the last value reported in the OEIS link, $a_{56}=221$, and e.g. $a_{100}=398$).

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}$ (written ${\rm f}\dashv{\bf u}$, meaning that ${\bf u}={\rm f }{\bf u'}$ for some ${\bf u'}\in\mathcal{A}^\mathbb{N}$), of length $n$, one has $w({\rm f })=h_{n+2}-h_{2}$.

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

$${\rm a}^5({\rm bc})^5\tau^2({\rm f}_k){\rm bcaabc}\dashv{\bf u}$$ whence ${\rm f}_{k+1}:={\rm a}^5({\rm bc})^5\tau^2({\rm f}_k){\rm bcaab}$ satisfies both ${\rm f}_{k+1}{\rm c}\dashv{\bf u}$ 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-1\ .$$ Also, the sequence of left factors ${\rm g}_k:={\rm a}^5\tau({\rm f_k})\dashv{\bf u}$ 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.

Pietro Majer
  • 60.5k
  • 4
  • 122
  • 269