A matrix dynamics approach to Golomb's recursion (Q1378506)

The purpose of this paper is the investigation of functions \(b\), defined on the positive integers and satisfying the recursion \(b(b(n)+kn)=2b(n)+kn\) for all \(n\in\mathbb{N}\) where \(k\in\mathbb{N}\) is a given parameter. It was remarked by S. W. Golomb in an unpublished preprint that the function \(b(n)=\lfloor n\rho\rfloor\) is such a function, where \(\rho\) is the positive root of the equation \(x^2+(k-2)x-k=0\). Contrary to a conjecture by Golomb, \textit{E. Barbeau} and \textit{S. Tanny} later showed that the recursion has infinitely many increasing solutions [cf. Electron. J. Comb. 3, R8 (1996; Zbl 0853.11011)]. In the present paper, the authors devise a new approach to this recursion. They consider the system of linear recursions \(u_{n+1} = ku_{n}+v_{n}\), \(v_{n+1}=ku_{n}+2v_{n}\) for \(n\in\mathbb{N}\). Then \(v_{1}=b(u_{1})\) implies \(v_{n}=b(u_{n})\) for all \(n\in\mathbb{N}\), and the new system is now open to matrix dynamics methods. In this way, the authors derive the asymptotic behaviour of any solution \(b\) on the subsequence \(u_n\), they prove that the function \(b(n)=\lfloor n\rho+\alpha\rfloor\) is a solution for every \(0\leq \alpha \leq 1\), and they give, for \(k=1\), the first example of a solution \(b\) which is not eventually increasing.