Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: Algebraic and analytic approaches collated

摘要

Among all sequences that satisfy a divide-and-conquer recurrence, those which are rational with respect to a numeration system are certainly the most basic and the most essential. Nevertheless, until recently this specific class of sequences has not been systematically studied from the asymptotic standpoint. We recall how a mechanical process designed by the author permits to compute their asymptotic expansions. The process is based on linear algebra, and involves computing Jordan normal forms, joint spectral radii, and solving dilation equations. The main contribution of the present article is the comparison between our algebraic method and the classical analytic number theory approach. Moreover, we develop new ways to compute the Fourier series of the periodic functions involved in the expansion. The article comes with an extended bibliography.