Asymptotic Analysis of q -Recursive Sequences.

For an integer q ≥ 2 , a q -recursive sequence is defined by recurrence relations on subsequences of indices modulo some powers of  q . In this article, q -recursive sequences are studied and the asymptotic behavior of their summatory functions is analyzed. It is shown that every q -recursive sequence is q -regular in the sense of Allouche and Shallit and that a q -linear representation of the sequence can be computed easily by using the coefficients from the recurrence relations. Detailed asymptotic results for q -recursive sequences are then obtained based on a general result on the asymptotic analysis of q -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.