Constant-recursive sequence
In mathematics and theoretical computer science, a constant-recursive sequence is an infinite sequence of numbers satisfying a linear recurrence relation: each number in the sequence is equal to a fixed linear combination of one or more of its immediate predecessors. A constant-recursive sequence is also known as a linear recurrence sequence, linear-recursive sequence, linear-recurrent sequence, or C-finite sequence. The most famous example of a constant-recursive sequence is the Fibonacci sequence, in which each number is the sum of the previous two; formally, we say that it satisfies a linear recurrence with  constant coefficients where formula_2 is the formula_3th Fibonacci number. Generalizing this idea, a constant-recursive sequence formula_4 satisfies a formula of the form where formula_6 are constants. In addition to the Fibonacci sequence, constant-recursive sequences include many other well-known sequences, such as arithmetic progressions, geometric progressions, and polynomials. Constant-recursive sequences arise in combinatorics and the theory of finite differences; in algebraic number theory, due to the relation of the sequence to the roots of a polynomial; in the analysis of algorithms in the running time of simple recursive functions; and in formal language theory, 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. A seminal result is the Skolem–Mahler–Lech theorem, which states that the zeros of a constant-recursive sequence have a regularly repeating (eventually periodic) form. On the other hand, the Skolem problem, which asks for algorithm to determine whether a linear recurrence has at least one zero, remains one of the unsolved problems in mathematics. Definition. An order-"d" homogeneous linear recurrence relation is an equation of the form where  the "d" coefficients formula_8 are coefficients ranging over the integers, rational numbers, algebraic numbers, real numbers, or complex numbers. A sequence formula_9 (written as formula_10 as a shorthand) ranging over the same domain as the coefficients, is constant-recursive if there is an order-"d" homogeneous linear recurrence with constant coefficients that it satisfies for all formula_11. This definition allows eventually-periodic sequences such as formula_12 and formula_13. Some authors require that formula_14, which excludes such sequences. The order of a constant-recursive sequence is the smallest formula_15 such that the sequence satisfies an order-"d" homogeneous linear recurrence, or formula_16 for  the everywhere-zero sequence. Equivalent definitions. In terms of matrices. A sequence formula_10 is constant-recursive of order formula_19 if and only if it can be written as where formula_21 is a formula_22 vector, formula_23 is a formula_24 matrix, and formula_25 is a formula_26 vector, where the elements come from the same domain (integers, rational numbers, algebraic numbers, real numbers, or complex numbers) as the original sequence. Specifically, formula_25 can be taken to be the first formula_28 values of the sequence, formula_23 the linear transformation that computes formula_30 from formula_31, and formula_21 the vector formula_33. In terms of vector spaces . A sequence formula_10 is constant-recursive if and only if the set of sequences is contained in a vector space whose dimension is finite, i.e. a finite-dimensional subspace of formula_36 closed under the left-shift operator. This is because the order-formula_28 linear recurrence relation can be understood as a proof of linear dependence between the vectors formula_38 for formula_39. An extension of this argument shows that the order of the sequence is equal to the dimension of the vector space generated by formula_38 for all formula_41. In terms of non-homogeneous linear recurrences. ! Non-homogeneous !! Homogeneous A non -homogeneous linear recurrence is an equation of the form where formula_47 is an additional constant. Any sequence satisfying a non-homogeneous linear recurrence is constant-recursive. This is because subtracting the equation for formula_48 from the equation for formula_49 yields a homogeneous recurrence for formula_50, from which we can solve for formula_49 to obtain In terms of generating functions. A sequence is constant-recursive precisely when its generating function is a rational function formula_55, where formula_56 and formula_57 are polynomials. 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 explicit derivation of the generating function in terms of the linear recurrence is where It follows from the above that the denominator here must be a polynomial not divisible by formula_60 (and in particular nonzero). Examples. 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 formula_61 with formula_62. For example, formula_63 and formula_64. The sequence 2, 1, 3, 4, 7, 11, ... of Lucas numbers satisfies the same recurrence as the Fibonacci  sequence but with initial conditions formula_65 and formula_66. More generally, every Lucas sequence is constant-recursive of order 2. Arithmetic progressions. For any formula_67 and any formula_68, the arithmetic progression formula_69 is constant-recursive of order 2, because it satisfies formula_43. Generalizing this, see polynomial sequences below. Geometric progressions. For any formula_71 and formula_41, the geometric progression formula_73 is constant-recursive of order 1, because it satisfies formula_74. This includes, for example, the sequence 1, 2, 4, 8, 16, ... as well as the rational number sequence formula_75. Eventually periodic sequences. A sequence that is eventually periodic with period length formula_76  is constant-recursive, since it satisfies formula_77 for all formula_11, where the order formula_28 is the length of the initial segment including the first repeating block. Examples of such sequences are 1, 0, 0, 0, ... (order 1) and 1, 6, 6, 6, ... (order 2). Polynomial sequences. A sequence defined by a polynomial formula_80 is constant-recursive. The sequence satisfies a recurrence of order formula_81 (where formula_28 is the degree of the polynomial), with coefficients given by the corresponding element of the binomial transform. The first few such equations are 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. Any sequence of formula_81 integer, real, or complex values can be used as initial conditions for a constant-recursive sequence of order formula_81. If the initial conditions lie on a polynomial of degree formula_89 or less, then the constant-recursive sequence also obeys a lower order equation. Enumeration of words in a regular language. Let formula_90 be a regular language, and let formula_49 be the number of words of length formula_3 in formula_90. Then formula_10 is constant-recursive. For example, formula_95 for  the language of all binary strings, formula_96 for the language of all unary strings, and formula_97 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 formula_98 over the semiring formula_99 is constant-recursive. Other examples. The sequences of Jacobsthal numbers, Padovan numbers, Pell numbers, and Perrin numbers are constant-recursive. 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 form where This characterization is exact: every  sequence of complex numbers that can be written in the above form is constant-recursive. For example, the Fibonacci number formula_2 is written in this form using Binet's formula: where formula_107 is the golden ratio and formula_108, both roots of the equation formula_109. In this case, formula_110, formula_111 for all formula_3, formula_113 (constant polynomials), formula_114, and formula_115. Notice that though the original sequence was over the integers, the closed form solution involves real or complex roots. In general, for sequences of integers or rationals, the closed formula will use algebraic numbers. The complex numbers formula_116 are derived as the  roots of the characteristic polynomial (or "auxiliary polynomial") of the recurrence: whose coefficients are the same as those of the recurrence. If the formula_28 roots formula_119 are all distinct, then the polynomials formula_120 are all constants, which can be determined from the initial values of the sequence. The term formula_101 is only needed when formula_122; if formula_123 then it corrects for the fact that some initial values may be exceptions to the general recurrence. In particular, formula_111 for all formula_102, the order of the sequence. In the general case where the roots of the characteristic polynomial are not necessarily distinct , and formula_126 is a root of multiplicity formula_127, the term formula_128 is multiplied by a degree-formula_129 polynomial in formula_3 (i.e. formula_120 in the formula has degree formula_127). For instance, if the characteristic polynomial factors as formula_133, with the same root "r" occurring three times, then the formula_3th term is of the form Closure properties. Constant-recursive sequences are closed under the following operations, where formula_136 denote constant-recursive sequences, formula_137 are their generating functions, and formula_138 are their orders, respectively. 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. The requirement formula_139 for Cauchy inverse is necessary for the case of integer sequences, but can be replaced by formula_140 if the sequence is over any field (rational, algebraic, real, or complex numbers). Behavior. Zeros. Despite simple local dynamics, constant-recursive functions exhibit complex global behavior. Define a "zero" of a constant-recursive sequence to be a nonnegative integer formula_3 such that formula_142. The Skolem–Mahler–Lech theorem states that the zeros of the sequence are eventually repeating: there exists constants formula_143 and formula_144 such that for all formula_145 , formula_142 if and only if formula_147. This result holds for a constant-recursive sequence over the complex numbers, or more generally, over any field of characteristic zero. Decision problems. The pattern of zeros in a constant-recursive sequence can also be investigated from the perspective of computability theory. To do so, the description of the sequence formula_49 must be given a finite description; this can be done if the sequence is over the integers or rational numbers, or even over the algebraic numbers. Given such an encoding for sequences formula_49, the following problems can be studied: Because the square of  a constant-recursive sequence formula_150 is still constant-recursive (see closure properties), the existence-of-a-zero problem in the table above reduces to positivity, and infinitely-many-zeros reduces to eventual positivity. Other problems also reduce to those in the above table: for example, whether formula_151 for some formula_3 reduces to existence-of-a-zero for the sequence formula_153. As a second example, for sequences in the real numbers, "weak" positivity (is formula_154 for all formula_3?) reduces to positivity of the sequence formula_156 (because the answer must be negated, this is a Turing reduction). The Skolem-Mahler-Lech theorem  would provide answers to some of these questions, except that its proof is non-constructive. It states that for all formula_145, the zeros are repeating; however, the value of formula_143 is not known to be computable, so this does not lead to a solution to the existence-of-a-zero problem. On the other hand, the exact pattern which repeats after formula_145 "is" computable. 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 sequences of order up to 4.