In mathematics, a constant-recursive sequence or C-finite sequence is a sequence satisfying a linear recurrence with constant coefficients.
Contents
Definition
An order-d homogeneous linear recurrence with constant coefficients is an equation of the form
where the d coefficients
A sequence
Equivalently,
is contained in a vector space whose dimension is finite.
Fibonacci sequence
The sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... of Fibonacci numbers satisfies the recurrence
with initial conditions
Explicitly, the recurrence yields the values
etc.
Lucas sequences
The sequence 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ... of Lucas numbers satisfies the same recurrence as the Fibonacci sequence but with initial conditions
More generally, every Lucas sequence is a constant-recursive sequence.
Geometric sequences
The geometric sequence
Eventually periodic sequences
A sequence that is eventually periodic with period length
Characterization in terms of exponential polynomials
The characteristic polynomial (or "auxiliary polynomial") of the recurrence is the polynomial
whose coefficients are the same as those of the recurrence. The nth term
where the coefficients ki are constants that can be determined by the initial conditions.
For the Fibonacci sequence, the characteristic polynomial is
More generally, if a root r of the characteristic polynomial has multiplicity m, then the term
where
Conversely, if there are polynomials
then
Characterization in terms of rational generating functions
A sequence is constant-recursive precisely when its generating function
is a rational function. The denominator is the polynomial obtained from the auxiliary polynomial by reversing the order of the coefficients, and the numerator is determined by the initial values of the sequence.
The generating function of the Fibonacci sequence is
In general, multiplying a generating function by the polynomial
yields a series
where
If
then
so we obtain the rational function
In the special case of a periodic sequence satisfying
by expanding the geometric series.
The generating function of the Catalan numbers is not a rational function, which implies that the Catalan numbers do not satisfy a linear recurrence with constant coefficients.
Closure properties
The termwise addition or multiplication of two constant-recursive sequences is again constant-recursive. This follows from the characterization in terms of exponential polynomials.
The Cauchy product of two constant-recursive sequences is constant-recursive. This follows from the characterization in terms of rational generating functions.
Sequences satisfying non-homogeneous recurrences
A sequence satisfying a non-homogeneous linear recurrence with constant coefficients is constant-recursive.
This is because the recurrence
can be solved for
Substituting this into the equation
shows that
of order
Generalizations
A natural generalization is obtained by relaxing the condition that the coefficients of the recurrence are constants. If the coefficients are allowed to be polynomials, then one obtains holonomic sequences.
A