In mathematics, an infinite sequence of numbers s 0 , s 1 , s 2 , s 3 , … {\displaystyle s_{0},s_{1},s_{2},s_{3},\ldots } is called constant-recursive if it satisfies an equation of the form
s n = c 1 s n − 1 + c 2 s n − 2 + ⋯ + c d s n − d , {\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d},}
for all n ≥ d {\displaystyle n\geq d} , where c i {\displaystyle c_{i}} 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
0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , … {\displaystyle 0,1,1,2,3,5,8,13,\ldots } , is constant-recursive because it satisfies the linear recurrence F n = F n − 1 + F n − 2 {\displaystyle F_{n}=F_{n-1}+F_{n-2}} : each number in the sequence is the sum of the previous two. Other examples include the power of two sequence 1 , 2 , 4 , 8 , 16 , … {\displaystyle 1,2,4,8,16,\ldots } , where each number is the sum of twice the previous number, and the square number sequence 0 , 1 , 4 , 9 , 16 , 25 , … {\displaystyle 0,1,4,9,16,25,\ldots } . All arithmetic progressions, all geometric progressions, and all polynomials are constant-recursive. However, not all sequences are constant-recursive; for example, the factorial sequence 1 , 1 , 2 , 6 , 24 , 120 , … {\displaystyle 1,1,2,6,24,120,\ldots } 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 (eventually periodic) 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 s 0 , s 1 , s 2 , s 3 , … {\displaystyle s_{0},s_{1},s_{2},s_{3},\ldots } (written as ( s n ) n = 0 ∞ {\displaystyle (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 + ⋯ + c d s n − d = ∑ k = 1 d c k s n − k , {\displaystyle 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 ≥ d , {\displaystyle n\geq d,} for some fixed coefficients c 1 , c 2 , … , c d {\displaystyle 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 {\displaystyle d} such that the sequence satisfies a recurrence of order d, or d = 0 {\displaystyle d=0} for the everywhere-zero sequence. The definition above allows eventually-periodic sequences such as 1 , 0 , 0 , 0 , … {\displaystyle 1,0,0,0,\ldots } and 0 , 1 , 0 , 0 , … {\displaystyle 0,1,0,0,\ldots } . Some authors require that c d ≠ 0 {\displaystyle c_{d}\neq 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 {\displaystyle F_{n}=F_{n-1}+F_{n-2}} with F 0 = 0 , F 1 = 1 {\displaystyle F_{0}=0,F_{1}=1} . For example, F 2 = F 1 + F 0 = 1 + 0 = 1 {\displaystyle F_{2}=F_{1}+F_{0}=1+0=1} and F 6 = F 5 + F 4 = 5 + 3 = 8 {\displaystyle 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 {\displaystyle L_{0}=2} and L 1 = 1 {\displaystyle L_{1}=1} . More generally, every Lucas sequence is constant-recursive of order 2.
Arithmetic progressions For any a {\displaystyle a} and any r ≠ 0 {\displaystyle r\neq 0} , the arithmetic progression a , a + r , a + 2 r , … {\displaystyle a,a+r,a+2r,\ldots } is constant-recursive of order 2, because it satisfies s n = 2 s n − 1 − s n − 2 {\displaystyle s_{n}=2s_{n-1}-s_{n-2}} . Generalizing this, see polynomial sequences below.
Geometric progressions For any a ≠ 0 {\displaystyle a\neq 0} and r {\displaystyle r} , the geometric progression a , a r , a r 2 , … {\displaystyle a,ar,ar^{2},\ldots } is constant-recursive of order 1, because it satisfies s n = r s n − 1 {\displaystyle s_{n}=rs_{n-1}} . This includes, for example, the sequence 1, 2, 4, 8, 16, ... as well as the rational number sequence 1 , 1 2 , 1 4 , 1 8 , 1 16 , . . . {\textstyle 1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},...} .
Eventually periodic sequences A sequence that is eventually periodic with period length ℓ {\displaystyle \ell } is constant-recursive, since it satisfies s n = s n − ℓ {\displaystyle s_{n}=s_{n-\ell }} for all n ≥ d {\displaystyle n\geq d} , where the order d {\displaystyle 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 + ⋯ + a d n d {\displaystyle 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 {\displaystyle d+1} (where d {\displaystyle 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 ⋅ s n − 1 {\displaystyle s_{n}=1\cdot s_{n-1}} for a degree 0 (that is, constant) polynomial,
s n = 2 ⋅ s n − 1 − 1 ⋅ s n − 2 {\displaystyle s_{n}=2\cdot s_{n-1}-1\cdot s_{n-2}} for a degree 1 or less polynomial,
s n = 3 ⋅ s n − 1 − 3 ⋅ s n − 2 + 1 ⋅ s n − 3 {\displaystyle 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 ⋅ s n − 1 − 6 ⋅ s n − 2 + 4 ⋅ s n − 3 − 1 ⋅ s n − 4 {\displaystyle 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 {\displaystyle d+1} integer, real, or complex values can be used as initial conditions for a constant-recursive sequence of order d + 1 {\displaystyle d+1} . If the initial conditions lie on a polynomial of degree d − 1 {\displaystyle d-1} or less, then the constant-recursive sequence also obeys a lower order equation.
Enumeration of words in a regular language Let L {\displaystyle L} be a regular language, and let s n {\displaystyle s_{n}} be the number of words of length n {\displaystyle n} in L {\displaystyle L} . Then ( s n ) n = 0 ∞ {\displaystyle (s_{n})_{n=0}^{\infty }} is constant-recursive. For example, s n = 2 n {\displaystyle s_{n}=2^{n}} for the language of all binary strings, s n = 1 {\displaystyle s_{n}=1} for the language of all unary strings, and s n = F n + 2 {\displaystyle 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 Σ = { a } {\displaystyle \Sigma =\{a\}} over the semiring ( R , + , × ) {\displaystyle (\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 , … {\displaystyle 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 , … {\displaystyle 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
A sequence ( s n ) n = 0 ∞ {\displaystyle (s_{n})_{n=0}^{\infty }} is constant-recursive of order less than or equal to d {\displaystyle d} if and only if it can be written as
s n = u A n v {\displaystyle s_{n}=uA^{n}v}
where u {\displaystyle u} is a 1 × d {\displaystyle 1\times d} vector, A {\displaystyle A} is a d × d {\displaystyle d\times d} matrix, and v {\displaystyle v} is a d × 1 {\displaystyle 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 {\displaystyle v} can be taken to be the first d {\displaystyle d} values of the sequence, A {\displaystyle A} the linear transformation that computes s n + 1 , s n + 2 , … , s n + d {\displaystyle s_{n+1},s_{n+2},\ldots ,s_{n+d}} from s n , s n + 1 , … , s n + d − 1 {\displaystyle s_{n},s_{n+1},\ldots ,s_{n+d-1}} , and u {\displaystyle u} the vector [ 0 , 0 , … , 0 , 1 ] {\displaystyle [0,0,\ldots ,0,1]} .
In terms of non-homogeneous linear recurrences
A non-homogeneous linear recurrence is an equation of the form
s n = c 1 s n − 1 + c 2 s n − 2 + ⋯ + c d s n − d + c {\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d}+c}
where c {\displaystyle c} is an additional constant. Any sequence satisfying a non-homogeneous linear recurrence is constant-recursive. This is because subtracting the equation for s n − 1 {\displaystyle s_{n-1}} from the equation for s n {\displaystyle s_{n}} yields a homogeneous recurrence for s n − s n − 1 {\displaystyle s_{n}-s_{n-1}} , from which we can solve for s n {\displaystyle s_{n}} to obtain
s n = ( c 1 + 1 ) s n − 1 + ( c 2 − c 1 ) s n − 2 + ⋯ + ( c d − c d − 1 ) s n − d − c d s n − d − 1 . {\displaystyle {\begin{aligned}s_{n}=&(c_{1}+1)s_{n-1}\\&+(c_{2}-c_{1})s_{n-2}+\dots +(c_{d}-c_{d-1})s_{n-d}\\&-c_{d}s_{n-d-1}.\end{aligned}}}
In terms of generating functions
A sequence is constant-recursive precisely when its generating function
∑ n = 0 ∞ s n x n = s 0 + s 1 x 1 + s 2 x 2 + s 3 x 3 + ⋯ {\displaystyle \sum _{n=0}^{\infty }s_{n}x^{n}=s_{0}+s_{1}x^{1}+s_{2}x^{2}+s_{3}x^{3}+\cdots }
is a rational function p ( x ) / q ( x ) {\displaystyle p(x)\,/\,q(x)} , where p {\displaystyle p} and q {\displaystyle q} are polynomials and q ( 0 ) = 1 {\displaystyle q(0)=1} . Moreover, the order of the sequence is the minimum d {\displaystyle d} such that it has such a form with deg q ( x ) ≤ d {\displaystyle {\text{deg }}q(x)\leq d} and deg p ( x ) < d {\displaystyle {\text{deg }}p(x)<d} . 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:
∑ n = 0 ∞ s n x n = b 0 + b 1 x 1 + b 2 x 2 + ⋯ + b d − 1 x d − 1 1 − c 1 x 1 − c 2 x 2 − ⋯ − c d x d , {\displaystyle \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 − ⋯ − c d s n − d . {\displaystyle 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 ) {\displaystyle q(x)} must be a polynomial not divisible by x {\displaystyle x} (and in particular nonzero).
In terms of sequence spaces
A sequence ( s n ) n = 0 ∞ {\displaystyle (s_{n})_{n=0}^{\infty }} is constant-recursive if and only if the set of sequences
{ ( s n + r ) n = 0 ∞ : r ≥ 0 } {\displaystyle \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 ∞ {\displaystyle (s_{n})_{n=0}^{\infty }} is contained in a finite-dimensional subspace of C N {\displaystyle \mathbb {C} ^{\mathbb {N} }} closed under the left-shift operator. This characterization is because the order- d {\displaystyle d} linear recurrence relation can be understood as a proof of linear dependence between the sequences ( s n + r ) n = 0 ∞ {\displaystyle (s_{n+r})_{n=0}^{\infty }} for r = 0 , … , d {\displaystyle 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 ∞ {\displaystyle (s_{n+r})_{n=0}^{\infty }} for all r {\displaystyle 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 + ⋯ + k e ( n ) r e n , {\displaystyle 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 ≥ 0 {\displaystyle n\geq 0} , where
The term z n {\displaystyle z_{n}} is a sequence which is zero for all n ≥ d {\displaystyle n\geq d} (where d {\displaystyle d} is the order of the sequence); The terms k 1 ( n ) , k 2 ( n ) , … , k e ( n ) {\displaystyle k_{1}(n),k_{2}(n),\ldots ,k_{e}(n)} are complex polynomials; and The terms r 1 , r 2 , … , r k {\displaystyle 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 {\displaystyle F_{n}} is written in this form using Binet's formula:
F n = 1 5 φ n − 1 5 ψ n , {\displaystyle F_{n}={\frac {1}{\sqrt {5}}}\varphi ^{n}-{\frac {1}{\sqrt {5}}}\psi ^{n},}
where φ = ( 1 + 5 ) / 2 ≈ 1.61803 … {\displaystyle \varphi =(1+{\sqrt {5}})\,/\,2\approx 1.61803\ldots } is the golden ratio and ψ = − 1 / φ {\displaystyle \psi =-1\,/\,\varphi } . These are the roots of the equation x 2 − x − 1 = 0 {\displaystyle x^{2}-x-1=0} . In this case, e = 2 {\displaystyle e=2} , z n = 0 {\displaystyle z_{n}=0} for all n {\displaystyle n} , k 1 ( n ) = k 2 ( n ) = 1 / 5 {\displaystyle k_{1}(n)=k_{2}(n)=1\,/\,{\sqrt {5}}} are both constant polynomials, r 1 = φ {\displaystyle r_{1}=\varphi } , and r 2 = ψ {\displaystyle r_{2}=\psi } . The term z n {\displaystyle z_{n}} is only needed when c d ≠ 0 {\displaystyle c_{d}\neq 0} ; if c d