Definability of Combinatorial Functions and Their Linear Recurrence Relations

T. Kotek, J. A. Makowsky

We consider functions of natural numbers which allow a combinatorial interpretation as density functions (speed) of classes of relational structures, s uch as Fibonacci numbers, Be…