Even more can be said: Theorem A provides an explicit q-linear representation of the sequence. One main result of this paper is that every q-recursive sequence is indeed q-regular see Sect. Linear Representation of q- Recursive Sequences. Here x( n) is one component of a vector v( n), and there exist matrices \(A_r\) with \(v(qn+r)=A_r v(n)\) for all \(0 \le r < q\) and \(n \ge 0\) see also Sect. Again the sequence h is an example, now for a 2-regular sequence it satisfies \(h(2^jn+r)=2^j h(n)\) for Footnote 2 \(n \ge 1\), \(j\ge 0\) and \(0\le r<2^j\), so every \(h(2^jn+r)\) can be written in terms of h( n).Įquivalently, every q-regular sequence can be modeled by a q-linear representation. 2 for more details and a precise description. One definition of a q-regular sequence x is that every subsequence of the form \(x(q^jn+r)\) can be written as a linear combination of the same finite number of sequences see Sect. The concept of q-recursive sequences is related to q-regular sequences introduced by Allouche and Shallit. ![]() Another example are divide-and-conquer recurrences, see. This is because the left-hand sides of the two recurrence relations contain \(2^1n\) shifted by 0 and 1, and because the right-hand sides only contain \(2^0n\) (and no shifts). A simple nontrivial example of such a sequence Footnote 1 is when h( n) is the largest power of 2 less than or equal to n see . It turns out that this property is quite natural and many combinatorial sequences are in fact q-recursive. Here q is an integer and at least 2, and q-recursive sequences are sequences which satisfy a specific type of recurrence relation: Roughly speaking, every subsequence whose indices run through a residue class modulo \(q^M\) is a linear combination of subsequences where for each of these subsequences, the indices run through a residue class modulo \(q^m\) for some \(m < M\). We study a special class of recursively defined sequences, the so-called q- recursive sequences. The number of unbordered factors in the Thue–Morse sequence.įor the first two sequences, our analysis even leads to precise formulæ without error terms. The number of non-zero elements in some generalized Pascal’s triangle and ![]() Three particular sequences are studied in detail: We discuss the asymptotic behavior of the summatory functions of Detailed asymptotic results for q-recursive sequences are then obtained based on a general result on the asymptotic analysis of q-regular sequences. 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. ![]() In this article, q-recursive sequences are studied and the asymptotic behavior of their summatory functions is analyzed. For an integer \(q\ge 2\), a q-recursive sequence is defined by recurrence relations on subsequences of indices modulo some powers of q.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |