- 1 Definition
- 2 Examples
- 3 Characterization in terms of exponential polynomials
- 4 Characterization in terms of rational generating functions
- 5 Closure properties
- 6 Sequences satisfying non-homogeneous recurrences
- 7 Generalizations
- 8 Notes
- 9 References
- 10 External links
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.
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
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.
The geometric sequence is constant-recursive, since it satisfies the recurrence for all .
Eventually periodic sequences
A sequence that is eventually periodic with period length is constant-recursive, since it satisfies for all for some d.
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 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 by 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
Conversely, if there are polynomials such that
then is constant-recursive.
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
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 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 to obtain
Substituting this into the equation
shows that satisfies the homogeneous recurrence
of order .
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 .
- 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.
- Martino, Ivan; Martino, Luca (2013-11-14). "On the variety of linear recurrences and numerical semigroups". Semigroup Forum. 88 (3): 569–574. doi:10.1007/s00233-013-9551-2. ISSN 0037-1912.
- Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association.
- Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics: A Foundation for Computer Science (2 ed.). Addison-Welsey. ISBN 0-201-55802-5.