# Simply generated sequences with mysterious differences

Suppose that $a_0 < a_1,$ $b_0 < b_1,$ and $$a_n=a_1b_{n-1}+a_0b_{n-2}+qn+r$$ for $n \geq 2$, where $a_0,a_1,b_0,b_1,q,r$ are integers such that $(a_n)$ and $(b_n)$ are increasing and ${(|a_n|)}$ and ${(|b_n|)}$ partition the positive integers. What can be proved about the cardinality of $$D=\{(a_n-a_{n-1},b_n-b_{n-1})\},$$ for $n \geq 0?$

Experimental results:

1. If $(a_0,a_1,b_0,b_1,q,r)=(-1,2,3,4,2,0)$, then $|D|=9$; see "Experimental fact" at A possibly surprising appearance of $\sqrt{2}.$

2. If $(a_0,a_1,b_0,b_1,q,r)=(1,2,3,4,1,0)$, then $D=\{(1,1),(4,1),(4,2),(5,1),(6,1),(11,1)\}.$

3. If $(a_0,a_1,b_0,b_1,q,r)=(3,4,1,2,1,-7)$, then $D=\{(1,1),(2,3),(8,1),(8,2),(11,1),(12,1),(16,2),(18,1)\}.$

Reasons for studying the set $D$ include these related questions:

1. Is $(a_n-a_{n-1})$ ever linearly recurrent?

2. Let $d$ be a number that occurs infinitely many times in $(b_n-b_{n-1})$, and let $(p_n)$ be the sequence of numbers $k$ such that $b_k-b_{k-1}=d.$ Must $(p_n/n)$ converge? As an example, for $(a_0,a_1,b_0,b_1,q,r)=(-1,2,3,4,2,0)$, we have $$(p_n) = (1,11,13,16,19,22,25,28,31,34,37,43,45,51,53,56,62,\dots),$$ and it appears that $\lim_{n \to \infty} p_n/n = 1+\sqrt{2}.$

• In Example 1, it is not clear $a_0=-1$, since it is required that $(a_n)$ and $(b_n)$ make a partition of the positive integers. After all, is there a reason why the coefficients in front of $b_{n-1}$ and $b_{n-2}$ must be exactly $a_1$ and $a_0$ and not some other integers $p$ and $s$ like $q$ and $r$? – Pietro Majer Jan 22 '18 at 15:19
• Pietro - As a quick fix, I added absolute values. – Clark Kimberling Jan 22 '18 at 15:33
• I think in example 1 we have $|D|=8$, I cannot see $(1,1)$ occurring. – Martin Rubey Jan 23 '18 at 6:55
• Is it (intuitively) clear that $|D|$ is also finite for longer "convolutions", eg. $a_n=\sum_{k=0}^2 a_k b_{n-3+k} + qn + r$? – Martin Rubey Jan 24 '18 at 8:54
• @MartinRubey Since $a_n-a_{n-1}=a_0(b_{n-1}-b_{n-2})+a_1(b_{n-2}-b_{n-3})+a_2(b_{n-3}-b_{n-4})+q$, arguing as in Pietro Majer's answer, if almost all $a_n−a_{n-1}$ are $>1$ then almost all $b_n−b_{n-1}$ are either $1$ or $2$, so that there are only finitely many possibilities for $a_n−a_{n−1}$. It is however not entirely clear what happens if (and how) infinitely many $a_n−a_{n-1}$ are $1$... – მამუკა ჯიბლაძე Jan 24 '18 at 21:32

This is less more than a long comment. It seems that a somehow simpler case is the when $a_{n+1}-a_n>1$ (at least eventually) which means $b_{n+1}-b_n\in\{1,2\}$ (eventually), and $a_{n+1}-a_n$ takes values in a finite set $\mathcal{A}$ of say $r$ integers greater or equal to $2$. Then the sequence $a_{n+1}-a_n$ is generated by a substitution map (like in the one described here or here, so that the entire sequence $a_{n+1}-a_n$, seen as an infinite string, has the form $p\cdot\tau(p)\cdot\tau(p)^2\cdot\tau(p)^3\dots$, where the dots stand for concatenation of words, and $p$ is a prefix. For such a substitution map $\tau$ one can write an associated $r\times r$ transition matrix $A:=(a_{ij})$ for the number of occurrences of each symbol in a transformed word: let $a_{ij}$ denote the number of occurrences of the letter $s_i$ in the word $\tau(s_j)$. Then, if in the vector $X$, $X_i$ is the number of occurrences of $s_i$ in a given word $w$, the coordinates of $AX$ give the number of occurrences of each $s_i$ in the word $\tau(w)$, so that, for $w=p$, the vector $A^k X$ gives the distribution of letters in $\tau(p^k)$; the length of $\tau(p^k)$ is the sum of coordinates of $A^{k-1} X$. This way the various asymptotics of $a_n$ can be easily related to the spectrum of $A$; in fact one use the standard techniques of finite Markov chains introducing a suitable Markov chain deduced from the map $\tau$. For instance, both quoted cases can be treated this way.
The case when $a_{n+1}-a_n$ can take the value $1$ frequently, so that $b_{n+1}-b_n$ assumes more values, seems less clear to me, but it may possibly be studied in the same lines.