Heuberger Clemens, Krenn Daniel, Lipnik Gabriel F
Alpen-Adria-Universität Klagenfurt, Klagenfurt, Austria.
Paris Lodron University of Salzburg, Salzburg, Austria.
Algorithmica. 2022;84(9):2480-2532. doi: 10.1007/s00453-022-00950-y. Epub 2022 May 4.
For an integer , a -recursive sequence is defined by recurrence relations on subsequences of indices modulo some powers of . In this article, -recursive sequences are studied and the asymptotic behavior of their summatory functions is analyzed. It is shown that every -recursive sequence is -regular in the sense of Allouche and Shallit and that a -linear representation of the sequence can be computed easily by using the coefficients from the recurrence relations. Detailed asymptotic results for -recursive sequences are then obtained based on a general result on the asymptotic analysis of -regular sequences. Three particular sequences are studied in detail: We discuss the asymptotic behavior of the summatory functions ofStern's diatomic sequence,the number of non-zero elements in some generalized Pascal's triangle andthe number of unbordered factors in the Thue-Morse sequence. For the first two sequences, our analysis even leads to precise formulæ without error terms.
对于整数 ，一个 -递归序列由关于模 的某些幂次的指标子序列的递归关系定义。在本文中，研究了 -递归序列并分析了它们的求和函数的渐近行为。结果表明，每个 -递归序列在阿卢什（Allouche）和沙利特（Shallit）的意义下是 -正则的，并且可以通过使用递归关系中的系数轻松计算该序列的 -线性表示。然后基于关于 -正则序列渐近分析的一个一般结果，得到了 -递归序列的详细渐近结果。详细研究了三个特定序列：我们讨论了斯特恩（Stern）双原子序列的求和函数的渐近行为、一些广义帕斯卡三角形中非零元素的数量以及图厄 - 摩尔斯（Thue-Morse）序列中无边界因子的数量。对于前两个序列，我们的分析甚至得出了没有误差项的精确公式。
