Some linear recurrences and their combinatorial interpretation by means ofregular 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 particula r, 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 lang uage, according to the ECO method, and the corresponding finite succession rule. (C) 2001 Elsevier Science B.V. All rights reserved.