Constant-recursive sequence

In mathematics, a constant-recursive sequence or C-finite sequence is a sequence satisfying a linear recurrence with constant coefficients.

DefinitionEdit

An order-d homogeneous linear recurrence with constant coefficients is an equation of the form

 

where the d coefficients   are constants.

A sequence   is a constant-recursive sequence if there is an order-d homogeneous linear recurrence with constant coefficients that it satisfies for all  .

Equivalently,   is constant-recursive if the set of sequences

 

is contained in a vector space whose dimension is finite.

ExamplesEdit

Fibonacci sequenceEdit

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 sequencesEdit

The sequence 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ... (sequence A000032 in the OEIS) 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 sequencesEdit

The geometric sequence   is constant-recursive, since it satisfies the recurrence   for all  .

Eventually periodic sequencesEdit

A sequence that is eventually periodic with period length   is constant-recursive, since it satisfies   for all   for some  .

Polynomial sequencesEdit

For any polynomial s(n), the sequence of its values is a constant-recursive sequence. If the degree of the polynomial is d, the sequence satisfies a recurrence of order  , with coefficients given by the corresponding element of the binomial transform.[1] The first few such equations are

  for a degree 0 (that is, constant) polynomial,
  for a degree 1 or less polynomial,
  for a degree 2 or less polynomial, and
  for a degree 3 or less polynomial.

A sequence obeying the order-d equation also obeys all higher order equations. These identities may be proved in a number of ways, including via the theory of finite differences.[citation needed] Each individual equation may also be verified by substituting the degree-d polynomial

 

where the coefficients   are symbolic. Any sequence of   integer, real, or complex values can be used as initial conditions for a constant-recursive sequence of order  . If the initial conditions lie on a polynomial of degree   or less, then the constant-recursive sequence also obeys a lower order equation.

Enumeration of words in a regular languageEdit

Let   be a regular language, and let   be the number of words of length   in  . Then   is constant-recursive.

Other examplesEdit

The sequences of Jacobsthal numbers, Padovan numbers, and Pell numbers are constant-recursive.

Characterization in terms of exponential polynomialsEdit

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   of a constant-recursive sequence can be written in terms of the roots of its characteristic polynomial. If the d roots   are all distinct, then the nth term of the sequence is

 

where the coefficients ki are constants that can be determined from the initial conditions.

For the Fibonacci sequence, the characteristic polynomial is  , whose roots   and   appear in Binet's formula

 

More generally, if a root r of the characteristic polynomial has multiplicity m, then the term   is multiplied by a degree-  polynomial in n. That is, let   be the distinct roots of the characteristic polynomial. Then

 

where   is a polynomial of degree  . For instance, if the characteristic polynomial factors as  , with the same root r occurring three times, then the nth term is of the form

 [2]

Conversely, if there are polynomials   such that

 

then   is constant-recursive.

Characterization in terms of rational generating functionsEdit

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.[3]

The generating function of the Fibonacci sequence is

 

In general, multiplying a generating function by the polynomial

 

yields a series

 

where

 

If   satisfies the recurrence relation

 

then   for all  . In other words,

 

so we obtain the rational function

 

In the special case of a periodic sequence satisfying   for  , the generating function is

 

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 propertiesEdit

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 recurrencesEdit

A sequence satisfying a non-homogeneous linear recurrence with constant coefficients is constant-recursive.

This is because the recurrence

 

can be solved for   to obtain

 

Substituting this into the equation

 

shows that   satisfies the homogeneous recurrence

 

of order  .

GeneralizationsEdit

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  -regular sequence satisfies linear recurrences with constant coefficients, but the recurrences take a different form. Rather than   being a linear combination of   for some integers   that are close to  , each term   in a  -regular sequence is a linear combination of   for some integers   whose base-  representations are close to that of  . Constant-recursive sequences can be thought of as  -regular sequences, where the base-1 representation of   consists of   copies of the digit  .

NotesEdit

  1. ^ Boyadzhiev, Boyad (2012). "Close Encounters with the Stirling Numbers of the Second Kind" (PDF). Math. Mag. 85: 252–266.
  2. ^ Greene, Daniel H.; Knuth, Donald E. (1982), "2.1.1 Constant coefficients – A) Homogeneous equations", Mathematics for the Analysis of Algorithms (2nd ed.), Birkhäuser, p. 17.
  3. ^ Martino, Ivan; Martino, Luca (2013-11-14). "On the variety of linear recurrences and numerical semigroups". Semigroup Forum. 88 (3): 569–574. arXiv:1207.0111. doi:10.1007/s00233-013-9551-2. ISSN 0037-1912.

ReferencesEdit

External linksEdit

  • "OEIS Index Rec". OEIS index to a few thousand examples of linear recurrences, sorted by order (number of terms) and signature (vector of values of the constant coefficients)