Constant-recursive sequence

A constant-recursive sequence is any sequence of integers, rational numbers, algebraic numbers, real numbers, or complex numbers s_0, s_1, s_2, s_3, \ldots (written as (s_n)_{n=0}^\infty as a shorthand) satisfying a formula of the form s_n = c_1 s_{n-1} + c_2 s_{n-2} + \dots + c_d s_{n-d} = \sum_{k=1}^d c_k s_{n-k}, for all n \ge d, for some fixed coefficients c_1, c_2, \dots, c_d ranging over the same domain as the sequence (integers, rational numbers, algebraic numbers, real numbers, or complex numbers). The equation is called a linear recurrence with constant coefficients of order d. The order of the sequence is the smallest positive integer d such that the sequence satisfies a recurrence of order d, or d = 0 for the everywhere-zero sequence. The definition above allows eventually-periodic sequences such as 1, 0, 0, 0, \ldots and 0, 1, 0, 0, \ldots. Some authors require that c_d \ne 0, which excludes such sequences. ==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 F_n = F_{n-1} + F_{n-2} with F_0 = 0, F_1 = 1. For example, F_2 = F_1 + F_0 = 1 + 0 = 1 and F_6 = F_5 + F_4 = 5 + 3 = 8. The sequence 2, 1, 3, 4, 7, 11, ... of Lucas numbers satisfies the same recurrence as the Fibonacci sequence but with initial conditions L_0 = 2 and L_1 = 1. More generally, every Lucas sequence is constant-recursive of order 2. Arithmetic progressions For any a and any r \ne 0, the arithmetic progression a, a+r, a+2r, \ldots is constant-recursive of order 2, because it satisfies s_n = 2s_{n-1} - s_{n-2}. Generalizing this, see polynomial sequences below. Geometric progressions For any a \ne 0 and r, the geometric progression a, a r, a r^2, \ldots is constant-recursive of order 1, because it satisfies s_n = r s_{n-1}. This includes, for example, the sequence 1, 2, 4, 8, 16, ... as well as the rational number sequence 1, \frac12, \frac14, \frac18, \frac{1}{16}, .... Eventually periodic sequences A sequence that is eventually periodic with period length \ell is constant-recursive, since it satisfies s_n = s_{n-\ell} for all n \geq d, where the order d 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 s_n = a_0 + a_1 n + a_2 n^2 + \cdots + a_d n^d is constant-recursive. The sequence satisfies a recurrence of order d + 1 (where d is the degree of the polynomial), with coefficients given by the corresponding element of the binomial transform. The first few such equations are : s_n = 1 \cdot s_{n-1} for a degree 0 (that is, constant) polynomial, : s_n = 2\cdot s_{n-1} - 1\cdot s_{n-2} for a degree 1 or less polynomial, : s_n = 3\cdot s_{n-1} - 3\cdot s_{n-2} + 1\cdot s_{n-3} for a degree 2 or less polynomial, and : s_n = 4\cdot s_{n-1} - 6\cdot s_{n-2} + 4\cdot s_{n-3} - 1\cdot s_{n-4} 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. Any sequence of d + 1 integer, real, or complex values can be used as initial conditions for a constant-recursive sequence of order d + 1. If the initial conditions lie on a polynomial of degree d - 1 or less, then the constant-recursive sequence also obeys a lower order equation. Enumeration of words in a regular language Let L be a regular language, and let s_n be the number of words of length n in L. Then (s_n)_{n=0}^\infty is constant-recursive. For example, s_n = 2^n for the language of all binary strings, s_n = 1 for the language of all unary strings, and s_n = F_{n+2} 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 \Sigma = \{a\} over the semiring (\mathbb{R}, +, \times) (which is in fact a ring, and even a field) 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 1, 1, 2, 6, 24, 120, 720, \ldots is not constant-recursive. More generally, every constant-recursive function is asymptotically bounded by an exponential function (see #Closed-form characterization) and the factorial sequence grows faster than this. The Catalan sequence 1, 1, 2, 5, 14, 42, 132, \ldots is not constant-recursive. This is because the generating function of the Catalan numbers is not a rational function (see #Equivalent definitions). ==Equivalent definitions==

In terms of matrices \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^n \begin{bmatrix}1 \\ 0\end{bmatrix}. A sequence (s_n)_{n=0}^\infty is constant-recursive of order less than or equal to d if and only if it can be written as :s_n = u A^n v where u is a 1 \times d vector, A is a d \times d matrix, and v is a d \times 1 vector, where the elements come from the same domain (integers, rational numbers, algebraic numbers, real numbers, or complex numbers) as the original sequence. Specifically, v can be taken to be the first d values of the sequence, A the linear transformation that computes s_{n+1}, s_{n+2}, \ldots, s_{n+d} from s_n, s_{n+1}, \ldots, s_{n+d-1}, and u the vector [0, 0, \ldots, 0, 1]. :\sum_{n = 0}^\infty s_n x^n = \frac{b_0 + b_1 x^1 + b_2 x^2 + \dots + b_{d-1} x^{d-1}}{1 - c_1 x^1 - c_2 x^2 - \dots - c_d x^d}, where :b_n = s_n - c_1 s_{n-1} - c_2 s_{n-2} - \dots - c_d s_{n-d}. It follows from the above that the denominator q(x) must be a polynomial not divisible by x (and in particular nonzero). In terms of sequence spaces A sequence (s_n)_{n=0}^\infty is constant-recursive if and only if the set of sequences :\left\{(s_{n+r})_{n=0}^\infty : r \geq 0\right\} is contained in a sequence space (vector space of sequences) whose dimension is finite. That is, (s_n)_{n=0}^\infty is contained in a finite-dimensional subspace of \mathbb{C}^\mathbb{N} closed under the left-shift operator. This characterization is because the order-d linear recurrence relation can be understood as a proof of linear dependence between the sequences (s_{n+r})_{n=0}^\infty for r=0, \ldots, d. An extension of this argument shows that the order of the sequence is equal to the dimension of the sequence space generated by (s_{n+r})_{n=0}^\infty for all r. == 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 :s_n = z_n + k_1(n) r_1^n + k_2(n) r_2^n + \cdots + k_e(n) r_e^n, for all n \ge 0, where • The term z_n is a sequence which is zero for all n \ge d (where d is the order of the sequence); • The terms k_1(n), k_2(n), \ldots, k_e(n) are complex polynomials; and • The terms r_1, r_2, \ldots, r_k are distinct complex constants. 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 F_n is written in this form using Binet's formula: :F_n = \frac{1}{\sqrt{5}}\varphi^n - \frac{1}{\sqrt{5}}\psi^n, where \varphi = (1 + \sqrt{5}) \,/\, 2 \approx 1.61803\ldots is the golden ratio and \psi = -1 \,/\, \varphi. These are the roots of the equation x^2 - x - 1 = 0. In this case, e=2, z_n = 0 for all n, k_1(n) = k_2(n) = 1 \,/\, \sqrt{5} are both constant polynomials, r_1 = \varphi, and r_2 = \psi. The term z_n is only needed when c_d\ne 0; if c_d = 0 then it corrects for the fact that some initial values may be exceptions to the general recurrence. In particular, z_n = 0 for all n \ge d. The complex numbers r_1, \ldots, r_n are the roots of the characteristic polynomial of the recurrence: :x^d - c_1 x^{d-1} - \dots - c_{d-1} x - c_d whose coefficients are the same as those of the recurrence. We call r_1, \ldots , r_n the characteristic roots of the recurrence. If the sequence consists of integers or rational numbers, the roots will be algebraic numbers. If the d roots r_1, r_2, \dots, r_d are all distinct, then the polynomials k_i(n) 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 r_i is a root of multiplicity m, then k_i(n) in the formula has degree m - 1. For instance, if the characteristic polynomial factors as (x-r)^3, with the same root r occurring three times, then the nth term is of the form s_n = (a + b n + c n^2) r^n. ==Closure properties==

Examples The sum of two constant-recursive sequences is also constant-recursive. For example, the sum of s_n = 2^n and t_n = n is u_n = 2^n + n (1, 3, 6, 11, 20, \ldots), which satisfies the recurrence u_n = 4u_{n-1} - 5u_{n-2} + 2u_{n-3}. The new recurrence can be found by adding the generating functions for each sequence. Similarly, the product of two constant-recursive sequences is constant-recursive. For example, the product of s_n = 2^n and t_n = n is u_n = n \cdot 2^n (0, 2, 8, 24, 64, \ldots), which satisfies the recurrence u_n = 4 u_{n-1} - 4 u_{n-2}. The left-shift sequence u_n = s_{n + 1} and the right-shift sequence u_n = s_{n - 1} (with u_0 = 0) are constant-recursive because they satisfy the same recurrence relation. For example, because s_n = 2^n is constant-recursive, so is u_n = 2^{n + 1}. List of operations In general, constant-recursive sequences are closed under the following operations, where s = (s_n)_{n \in \mathbb{N}}, t = (t_n)_{n \in \mathbb{N}} denote constant-recursive sequences, f(x), g(x) are their generating functions, and d, e 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 s_0 = 1 for Cauchy inverse is necessary for the case of integer sequences, but can be replaced by s_0 \ne 0 if the sequence is over any field (rational, algebraic, real, or complex numbers). ==Behavior==

Zeros Despite satisfying a simple local formula, a constant-recursive sequence can exhibit complicated global behavior. Define a zero of a constant-recursive sequence to be a nonnegative integer n such that s_n = 0. The Skolem–Mahler–Lech theorem states that the zeros of the sequence are eventually repeating: there exists constants M and N such that for all n > M, s_n = 0 if and only if s_{n+N} = 0. 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 s_n must be given a finite description; this can be done if the sequence is over the integers, rational numbers, or algebraic numbers. Given such an encoding for sequences s_n, the following problems can be studied: Because the square of a constant-recursive sequence s_n^2 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 s_n = c for some n reduces to existence-of-a-zero for the sequence s_n - c. As a second example, for sequences in the real numbers, weak positivity (is s_n \ge 0 for all n?) reduces to positivity of the sequence -s_n (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 n > M, the zeros are repeating; however, the value of M is not known to be computable, so this does not lead to a solution to the existence-of-a-zero problem. 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. It is also known to be decidable for reversible integer sequences up to order 7, that is, sequences that may be continued backwards in the integers. Degeneracy Let r_1, \ldots, r_n be the characteristic roots of a constant recursive sequence s. We say that the sequence is degenerate if the ratio r_i/r_j is a root of unity, for any i \neq j. It is often easier to study non-degenerate sequences, and one can reduce to this using the following theorem: if s has order d and is contained in a number field K of degree k over \mathbb Q , then there is a constant M(k,d) \leq \begin{cases} \exp(2d (3\log d)^{1/2}) & \text{if } k = 1, \\ 2^{kd+1} & \text{if } k \geq 2 \end{cases} such that for some M \leq M(k,d) each subsequence s_{Mn+\ell} is either identically zero or non-degenerate. ==Generalizations==

A D-finite or holonomic sequence is a natural generalization where the coefficients of the recurrence are allowed to be polynomial functions of n rather than constants. A k-regular sequence satisfies a linear recurrences with constant coefficients, but the recurrences take a different form. Rather than s_n being a linear combination of s_m for some integers m that are close to n, each term s_n in a k-regular sequence is a linear combination of s_m for some integers m whose base-k representations are close to that of n. Constant-recursive sequences can be thought of as 1-regular sequences, where the base-1 representation of n consists of n copies of the digit 1. ==Notes==