Recurrent sequences and affine functional equations (Q1912304)

An arithmetic function \(f:\mathbb{N}\to\mathbb{C}\) is called recurrent if there are complex constants \(a_0,\dots,a_{k-1}\), \(a_0\neq 0\), such that \[ f(n+k)+a_{k-1}f(n+k-1)+\dots+a_1f(n+1)+a_0f(n)=0\tag{1} \] holds for all natural numbers \(n\). If (1) is satisfied for large values of \(n\) only then \(f\) is called ultimately recurrent. Several authors characterized multiplicative and additive functions \(f\) which are recurrent or ultimately recurrent. In the present paper the authors explain a more general concept: A function \(f:\mathbb{N}\to\mathbb{C}\) is called affinely reducible if there exist arbitrary large numbers \(N\), \(q\in\mathbb{N}\) and \(a\in\mathbb{N}_0\) such that \[ f(qn+a)=q^*f(n)+a^*,\qquad 1\leq n\leq N,\tag{2} \] holds with coefficients \(q^*,a^*\in\mathbb{C}\), \(q^*\neq 0\), depending at most on \(q\) and \(a\). Besides multiplicative and additive functions, (2) is satisfied by functions of the form \[ f(n)=\alpha+(n+\gamma)^s h(n),\quad\alpha,s\in\mathbb{C}, \gamma\in\mathbb{Q},\;\gamma\geq 0, \] \(h\) periodic. The authors show that all affine reducible and ultimately recurrent functions are of this type. The proofs are based on solutions of certain functional equations and use properties of the companion polynomial \(p(z)=z^k+a_{k-1}z^{k-1}+\dots+a_1z+a_0\) of the equation (1).