On digit expansions with respect to linear recurrences (Q1122608): Difference between revisions

Let \(G=(G_k)\) be a linear recurring sequence \(G_{k+d}=a_1G_{k+d-1}+\cdots+a_dG_k\) with integral coefficients \(a_1\ge\cdots\ge a_{d-1}\ge a_d>0\) and integral initial values \(1=G_0,\ldots, G_{d-1}\) satisfying \(a_1>1\) (for \(d=1)\) and for \(d\ge 2\) \[ G_k\ge a_1G_{k-1}+\cdots+a_nG_0+1\quad\text{for } n=1,\ldots,d-1. \] Then every positive integer \(n\) can be represented in a unique way by \(\sum \varepsilon_jG_j\) where the \(G\)-ary digits \(\varepsilon_j=\varepsilon_j(n)\) are integers with \(0\le \varepsilon_j<a_1\) satisfying some additional conditions (Theorem 1). The main results are concerned with the sum-of-digit function \(s(n)=\sum \varepsilon_j(n)\) with respect to a given linear recurrence as above. The following asymptotic formula is proved: \[ (1/N)\sum_{n<N}s(n)=c \log N+F((\log N)/(\log \alpha))+O(\log N/N), \] where \(c>0\) is a constant, \(\alpha\) the dominating characteristic root of \(G\) and \(F\) is a bounded nowhere differentiable function. If the initial values are minimal \(F\) is periodic with period 1 and continuous. In the case of a second-order linear recurrence, \(F\) is periodic and continuous if and only if \(G_1=a_1+1\). For \(a_1=a_2=1\), this is a characterization of the Fibonacci numbers. This case was considered by \textit{J. Coquet} and \textit{P. Van den Bosch} [J. Number Theory 22, 139--146 (1986; Zbl 0578.10010)]. [Remark: Because of computational errors some results are stated somewhat different.]