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

  • $\begingroup$ 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$? $\endgroup$ Commented Jan 22, 2018 at 15:19
  • $\begingroup$ Pietro - As a quick fix, I added absolute values. $\endgroup$ Commented Jan 22, 2018 at 15:33
  • 1
    $\begingroup$ I think in example 1 we have $|D|=8$, I cannot see $(1,1)$ occurring. $\endgroup$ Commented Jan 23, 2018 at 6:55
  • 1
    $\begingroup$ 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$? $\endgroup$ Commented Jan 24, 2018 at 8:54
  • 1
    $\begingroup$ @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$... $\endgroup$ Commented Jan 24, 2018 at 21:32

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.