Regular Sequences

Regular Sequences

Regular sequences were introduced by Allouche and Shallit in 1992. Examples appear frequently in number theory, combinatorics, and computer science. In many ways, a regular sequence is analogous to a sequence satisfying a linear recurrence with constant coefficients. The difference is that, in a linear recurrence, a(n) and a(m) are related when n and m are close in the real metric; whereas for a k-regular sequence a(n) and a(m) are related when the base-k representations of n and m are similar. In this talk we will discuss some recent activity in the study of k-regular sequences, and we will examine how the class of k-regular sequences fits into the larger context of integer sequences that arise naturally in combinatorics.