Constant-recursive sequence
In mathematics,[] an infinite sequence of numbers is called constant-recursive if it satisfies an equation of the form
for all, where are constants. The equation is called a linear recurrence relation.
The concept is also known as a linear recurrence sequence, linear-recursive sequence, linear-recurrent sequence, or a C-finite sequence.
For example, the Fibonacci sequence
is constant-recursive because it satisfies the linear recurrence : each number in the sequence is the sum of the previous two.
Other examples include the power of two sequence, where each number is the sum of twice the previous number, and the square number sequence. All arithmetic progressions, all geometric progressions, and all polynomials are constant-recursive. However, not all sequences are constant-recursive; for example, the factorial sequence is not constant-recursive.
Constant-recursive sequences are studied in combinatorics and the theory of finite differences. They also arise in algebraic number theory, due to the relation of the sequence to polynomial roots; in the analysis of algorithms, as the running time of simple recursive functions; and in the theory of formal languages, where they count strings up to a given length in a regular language. Constant-recursive sequences are closed under important mathematical operations such as term-wise addition, term-wise multiplication, and Cauchy product.
The Skolem–Mahler–Lech theorem states that the zeros of a constant-recursive sequence have a regularly repeating form. The Skolem problem, which asks for an algorithm to determine whether a linear recurrence has at least one zero, is an unsolved problem in mathematics.
Definition
A constant-recursive sequence is any sequence of integers, rational numbers, algebraic numbers, real numbers, or complex numbers satisfying a formula of the formfor all for some fixed coefficients ranging over the same domain as the sequence.
The equation is called a linear recurrence with constant coefficients of order d.
The order of the sequence is the smallest positive integer such that the sequence satisfies a recurrence of order d, or for the everywhere-zero sequence.
The definition above allows eventually-periodic sequences such as and. Some authors require that, which excludes such sequences.
Examples
| Name | Order | First few values | Recurrence | Generating function | OEIS |
| Zero sequence | 0 | 0, 0, 0, 0, 0, 0,... | |||
| One sequence | 1 | 1, 1, 1, 1, 1, 1,... | |||
| Characteristic function of | 1 | 1, 0, 0, 0, 0, 0, ... | |||
| Powers of two | 1 | 1, 2, 4, 8, 16, 32,... | |||
| Powers of −1 | 1 | 1, −1, 1, −1, 1, −1,... | |||
| Characteristic function of | 2 | 0, 1, 0, 0, 0, 0,... | |||
| Decimal expansion of 1/6 | 2 | 1, 6, 6, 6, 6, 6,... | |||
| Decimal expansion of 1/11 | 2 | 0, 9, 0, 9, 0, 9,... | |||
| Nonnegative integers | 2 | 0, 1, 2, 3, 4, 5,... | |||
| Odd positive integers | 2 | 1, 3, 5, 7, 9, 11,... | |||
| Fibonacci numbers | 2 | 0, 1, 1, 2, 3, 5, 8, 13,... | |||
| Lucas numbers | 2 | 2, 1, 3, 4, 7, 11, 18, 29,... | |||
| Pell numbers | 2 | 0, 1, 2, 5, 12, 29, 70,... | |||
| Powers of two interleaved with 0s | 2 | 1, 0, 2, 0, 4, 0, 8, 0,... | |||
| Reciprocal of 6th cyclotomic polynomial | 2 | 1, 1, 0, −1, −1, 0, 1, 1,... | |||
| Triangular numbers | 3 | 0, 1, 3, 6, 10, 15, 21,... |
Fibonacci and Lucas sequences
The sequence 0, 1, 1, 2, 3, 5, 8, 13,... of Fibonacci numbers is constant-recursive of order 2 because it satisfies the recurrence with. For example, and. The sequence 2, 1, 3, 4, 7, 11,... of Lucas numbers satisfies the same recurrence as the Fibonacci sequence but with initial conditions and. More generally, every Lucas sequence is constant-recursive of order 2.Arithmetic progressions
For any and any, the arithmetic progression is constant-recursive of order 2, because it satisfies. Generalizing this, see polynomial sequences below.Geometric progressions
For any and, the geometric progression is constant-recursive of order 1, because it satisfies. This includes, for example, the sequence 1, 2, 4, 8, 16,... as well as the rational number sequence.Eventually periodic sequences
A sequence that is eventually periodic with period length is constant-recursive, since it satisfies for all, where the order is the length of the initial segment including the first repeating block. Examples of such sequences are 1, 0, 0, 0,... and 1, 6, 6, 6,....Polynomial sequences
A sequence defined by a polynomial is constant-recursive. The sequence satisfies a recurrence of order , with coefficients given by the corresponding element of the binomial transform. The first few such equations areA 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.
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 language
Let be a regular language, and let be the number of words of length in. Then is constant-recursive. For example, for the language of all binary strings, for the language of all unary strings, and for the language of all binary strings that do not have two consecutive ones. More generally, any function accepted by a weighted automaton over the unary alphabet over the semiring is constant-recursive.Other examples
The sequences of Jacobsthal numbers, Padovan numbers, Pell numbers, and Perrin numbers are constant-recursive.Non-examples
The factorial sequence is not constant-recursive. More generally, every constant-recursive function is asymptotically bounded by an exponential function and the factorial sequence grows faster than this.The Catalan sequence is not constant-recursive. This is because the generating function of the Catalan numbers is not a rational function.
Equivalent definitions
In terms of matrices
A sequence is constant-recursive of order less than or equal to if and only if it can be written aswhere is a vector, is a matrix, and is a vector, where the elements come from the same domain as the original sequence. Specifically, can be taken to be the first values of the sequence, the linear transformation that computes from, and the vector.
In terms of non-homogeneous linear recurrences
! Non-homogeneous !! HomogeneousA non-homogeneous linear recurrence is an equation of the form
where is an additional constant. Any sequence satisfying a non-homogeneous linear recurrence is constant-recursive. This is because subtracting the equation for from the equation for yields a homogeneous recurrence for, from which we can solve for to obtain
In terms of generating functions
A sequence is constant-recursive precisely when its generating functionis a rational function, where and are polynomials and.
Moreover, the order of the sequence is the minimum such that it has such a form with and.
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:
where
It follows from the above that the denominator must be a polynomial not divisible by .
In terms of sequence spaces
A sequence is constant-recursive if and only if the set of sequencesis contained in a sequence space whose dimension is finite. That is, is contained in a finite-dimensional subspace of closed under the left-shift operator.
This characterization is because the order- linear recurrence relation can be understood as a proof of linear dependence between the sequences for. An extension of this argument shows that the order of the sequence is equal to the dimension of the sequence space generated by for all.
Closed-form characterization
Constant-recursive sequences admit the following unique closed form characterization using exponential polynomials: every constant-recursive sequence can be written in the formfor all, where
- The term is a sequence which is zero for all ;
- The terms are complex polynomials; and
- The terms are distinct complex constants.
For example, the Fibonacci number is written in this form using Binet's formula:
where is the golden ratio and. These are the roots of the equation. In this case,, for all, are both constant polynomials,, and.
The term is only needed when ; if then it corrects for the fact that some initial values may be exceptions to the general recurrence. In particular, for all.
The complex numbers are the roots of the characteristic polynomial of the recurrence:
whose coefficients are the same as those of the recurrence.
We call the characteristic roots of the recurrence. If the sequence consists of integers or rational numbers, the roots will be algebraic numbers.
If the roots are all distinct, then the polynomials are all constants, which can be determined from the initial values of the sequence.
If the roots of the characteristic polynomial are not distinct, and is a root of multiplicity, then in the formula has degree. For instance, if the characteristic polynomial factors as, with the same root r occurring three times, then the th term is of the form