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}.$](https://mathoverflow.net/questions/290808/a-possibly-surprising-appearance-of-sqrt2?noredirect=1&lq=1)
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}.$



Simply generated sequences with mysterious differences
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](https://mathoverflow.net/questions/290220/limit-associated-with-complementary-sequences) or [here](https://mathoverflow.net/questions/290808/a-possibly-surprising-appearance-of-sqrt2?noredirect=1&lq=1), 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.


