Constant-recursive sequence
[1] For example, the Fibonacci sequence is constant-recursive because it satisfies the linear recurrence
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.
The Skolem–Mahler–Lech theorem states that the zeros of a constant-recursive sequence have a regularly repeating (eventually periodic) form.
[3][4][5] The sequence 0, 1, 1, 2, 3, 5, 8, 13, ... of Fibonacci numbers is constant-recursive of order 2 because it satisfies the recurrence
is the length of the initial segment including the first repeating block.
is the degree of the polynomial), with coefficients given by the corresponding element of the binomial transform.
These identities may be proved in a number of ways, including via the theory of finite differences.
integer, real, or complex values can be used as initial conditions for a constant-recursive sequence of order
More generally, any function accepted by a weighted automaton over the unary alphabet
, where This characterization is exact: every sequence of complex numbers that can be written in the above form is constant-recursive.
then it corrects for the fact that some initial values may be exceptions to the general recurrence.
The new recurrence can be found by adding the generating functions for each sequence.
[27] The closure under term-wise addition and multiplication follows from the closed-form characterization in terms of exponential polynomials.
The closure under Cauchy product follows from the generating function characterization.
for Cauchy inverse is necessary for the case of integer sequences, but can be replaced by
if the sequence is over any field (rational, algebraic, real, or complex numbers).
[27] Despite satisfying a simple local formula, a constant-recursive sequence can exhibit complicated global behavior.
The Skolem–Mahler–Lech theorem states that the zeros of the sequence are eventually repeating: there exists constants
This result holds for a constant-recursive sequence over the complex numbers, or more generally, over any field of characteristic zero.
[30] The pattern of zeros in a constant-recursive sequence can also be investigated from the perspective of computability theory.
As a second example, for sequences in the real numbers, weak positivity (is
The Skolem-Mahler-Lech theorem would provide answers to some of these questions, except that its proof is non-constructive.
[11][32] This is why the infinitely-many-zeros problem is decidable: just determine if the infinitely-repeating pattern is empty.
Decidability results are known when the order of a sequence is restricted to be small.
For example, the Skolem problem is decidable for algebraic sequences of order up to 4.
[31] Decidability results are also known under the assumption of certain unproven conjectures in number theory.
For example, decidability is known for rational sequences of order up to 5 subject to the Skolem conjecture (also known as the exponential local-global principle).
It is often easier to study non-degenerate sequences, in a certain sense one can reduce to this using the following theorem: if
[37] A D-finite or holonomic sequence is a natural generalization where the coefficients of the recurrence are allowed to be polynomial functions of
