C-Finite Sequences and Riordan Arrays

Source abstract

Many prominent combinatorial sequences, such as the Fibonacci, Lucas, Pell, Jacobsthal and Tribonacci sequences, are defined by homogeneous linear recurrence relations with constant coefficients. These sequences are often referred to as C-finite sequences, and a variety of representations have been employed throughout the literature, largely influenced by the author’s background and the specific application under consideration. Beyond the representation through recurrence relations, other approaches include those based on generating functions, explicit formulas, matrix exponentiation, the method of undetermined coefficients and several others. Among these, the generating function approach is particularly prevalent in enumerative combinatorics due to its versatility and widespread use. The primary objective of this work is to introduce an alternative representation grounded in the theory of Riordan arrays. This representation provides a general formula expressed in terms of the vectors of constants and initial conditions associated with any recurrence relation of a given order, offering a new perspective on the structure of such sequences.