A k-regular sequence is an infinite sequence satisfying recurrence equations of a certain type, in which the nth term is a linear combination of mth terms for some integers m whose base-k representations are close to that of n.
Contents
Regular sequences generalize automatic sequences to infinite alphabets.
Definition
Let
is contained in a finite-dimensional vector space over the field of rational numbers.
Ruler sequence
Let
is contained in the
which, along with initial conditions
Thue–Morse sequence
Every k-automatic sequence is k-regular. For example, the Thue–Morse sequence
consists of the two sequences
Polynomial sequences
If
Properties
The class of k-regular sequences is closed under termwise addition and multiplication.
The nth term in a k-regular sequence grows at most polynomially in n.
Generalizations
The notion of a k-regular sequence can be generalized to a ring
is finitely generated.