Some linear recurrences and their combinatorial interpretation by means of regular languages
In this paper we apply ECO method and the concept of numeration systems to give a combinatorial interpretation to linear recurrences of the kind a(n) = ka(n-1) + ha(n-2), where k > /h/ greater than or equal to 0. In particular, we define a language L such that the words of L having length n satisfy the recurrence, and then we describe a recursive construction for this language, according to the ECO method, and the corresponding finite succession rule. (C) 2001 Elsevier Science B.V. All rights reserved.
regular languages numeration systems succession rules linear recurrence relations