Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Constant-recursive sequence
Sequence satisfying a homogeneous linear recurrence with constant coefficients

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.

We don't have any images related to Constant-recursive sequence yet.
We don't have any YouTube videos related to Constant-recursive sequence yet.
We don't have any PDF documents related to Constant-recursive sequence yet.
We don't have any Books related to Constant-recursive sequence yet.
We don't have any archived web articles related to Constant-recursive sequence yet.

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 , {\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,} 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.345

Examples

Selected examples of integer constant-recursive sequences6
NameOrder ( d {\displaystyle d}   )First few valuesRecurrence (for n ≥ d {\displaystyle n\geq d}  )Generating functionOEIS
Zero sequence00, 0, 0, 0, 0, 0, ... s n = 0 {\displaystyle s_{n}=0} 0 1 {\displaystyle {\frac {0}{1}}} A000004
One sequence11, 1, 1, 1, 1, 1, ... s n = s n − 1 {\displaystyle s_{n}=s_{n-1}} 1 1 − x {\displaystyle {\frac {1}{1-x}}} A000012
Characteristic function of { 0 } {\displaystyle \{0\}} 11, 0, 0, 0, 0, 0, ... s n = 0 {\displaystyle s_{n}=0} 1 1 {\displaystyle {\frac {1}{1}}} A000007
Powers of two11, 2, 4, 8, 16, 32, ... s n = 2 s n − 1 {\displaystyle s_{n}=2s_{n-1}} 1 1 − 2 x {\displaystyle {\frac {1}{1-2x}}} A000079
Powers of −111, −1, 1, −1, 1, −1, ... s n = − s n − 1 {\displaystyle s_{n}=-s_{n-1}} 1 1 + x {\displaystyle {\frac {1}{1+x}}} A033999
Characteristic function of { 1 } {\displaystyle \{1\}} 20, 1, 0, 0, 0, 0, ... s n = 0 {\displaystyle s_{n}=0} x 1 {\displaystyle {\frac {x}{1}}} A063524
Decimal expansion of 1/621, 6, 6, 6, 6, 6, ... s n = s n − 1 {\displaystyle s_{n}=s_{n-1}} 1 + 5 x 1 − x {\displaystyle {\frac {1+5x}{1-x}}} A020793
Decimal expansion of 1/1120, 9, 0, 9, 0, 9, ... s n = s n − 2 {\displaystyle s_{n}=s_{n-2}} 9 x 1 − x 2 {\displaystyle {\frac {9x}{1-x^{2}}}} A010680
Nonnegative integers20, 1, 2, 3, 4, 5, ... s n = 2 s n − 1 − s n − 2 {\displaystyle s_{n}=2s_{n-1}-s_{n-2}} x ( 1 − x ) 2 {\displaystyle {\frac {x}{(1-x)^{2}}}} A001477
Odd positive integers21, 3, 5, 7, 9, 11, ... s n = 2 s n − 1 − s n − 2 {\displaystyle s_{n}=2s_{n-1}-s_{n-2}} 1 + x ( 1 − x ) 2 {\displaystyle {\frac {1+x}{(1-x)^{2}}}} A005408
Fibonacci numbers20, 1, 1, 2, 3, 5, 8, 13, ... s n = s n − 1 + s n − 2 {\displaystyle s_{n}=s_{n-1}+s_{n-2}} x 1 − x − x 2 {\displaystyle {\frac {x}{1-x-x^{2}}}} A000045
Lucas numbers22, 1, 3, 4, 7, 11, 18, 29, ... s n = s n − 1 + s n − 2 {\displaystyle s_{n}=s_{n-1}+s_{n-2}} 2 − x 1 − x − x 2 {\displaystyle {\frac {2-x}{1-x-x^{2}}}} A000032
Pell numbers20, 1, 2, 5, 12, 29, 70, ... s n = 2 s n − 1 + s n − 2 {\displaystyle s_{n}=2s_{n-1}+s_{n-2}} x 1 − 2 x − x 2 {\displaystyle {\frac {x}{1-2x-x^{2}}}} A000129
Powers of two interleaved with 0s21, 0, 2, 0, 4, 0, 8, 0, ... s n = 2 s n − 2 {\displaystyle s_{n}=2s_{n-2}} 1 1 − 2 x 2 {\displaystyle {\frac {1}{1-2x^{2}}}} A077957
Inverse of 6th cyclotomic polynomial21, 1, 0, −1, −1, 0, 1, 1, ... s n = s n − 1 − s n − 2 {\displaystyle s_{n}=s_{n-1}-s_{n-2}} 1 1 − x + x 2 {\displaystyle {\frac {1}{1-x+x^{2}}}} A010892
Triangular numbers30, 1, 3, 6, 10, 15, 21, ... s n = 3 s n − 1 − 3 s n − 2 + s n − 3 {\displaystyle s_{n}=3s_{n-1}-3s_{n-2}+s_{n-3}} x ( 1 − x ) 3 {\displaystyle {\frac {x}{(1-x)^{3}}}} A000217

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.7

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.89 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.10 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.11 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 numbers12 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

Main article: Companion matrix

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]} .13

In terms of non-homogeneous linear recurrences

Main article: Linear recurrence with constant coefficients § Conversion to homogeneous form

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} .14 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} .15

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:1617

∑ 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}.} 18

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.1920

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} .2122

Closed-form characterization

For a derivation of the closed form, see Linear recurrence with constant coefficients § General solution.

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.2324

This characterization is exact: every sequence of complex numbers that can be written in the above form is constant-recursive.25

For example, the Fibonacci number F n {\displaystyle F_{n}} is written in this form using Binet's formula:26

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 = 0 {\displaystyle 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 {\displaystyle z_{n}=0} for all n ≥ d {\displaystyle n\geq d} .

The complex numbers r 1 , … , r n {\displaystyle r_{1},\ldots ,r_{n}} are the roots of the characteristic polynomial of the recurrence:

x d − c 1 x d − 1 − ⋯ − c d − 1 x − c d {\displaystyle x^{d}-c_{1}x^{d-1}-\dots -c_{d-1}x-c_{d}}

whose coefficients are the same as those of the recurrence.27 We call r 1 , … , r n {\displaystyle 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 {\displaystyle d} roots r 1 , r 2 , … , r d {\displaystyle r_{1},r_{2},\dots ,r_{d}} are all distinct, then the polynomials k i ( n ) {\displaystyle 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 {\displaystyle r_{i}} is a root of multiplicity m {\displaystyle m} , then k i ( n ) {\displaystyle k_{i}(n)} in the formula has degree m − 1 {\displaystyle m-1} . For instance, if the characteristic polynomial factors as ( x − r ) 3 {\displaystyle (x-r)^{3}} , with the same root r occurring three times, then the n {\displaystyle n} th term is of the form s n = ( a + b n + c n 2 ) r n . {\displaystyle s_{n}=(a+bn+cn^{2})r^{n}.} 2829

Closure properties

Examples

The sum of two constant-recursive sequences is also constant-recursive.3031 For example, the sum of s n = 2 n {\displaystyle s_{n}=2^{n}} and t n = n {\displaystyle t_{n}=n} is u n = 2 n + n {\displaystyle u_{n}=2^{n}+n} ( 1 , 3 , 6 , 11 , 20 , … {\displaystyle 1,3,6,11,20,\ldots } ), which satisfies the recurrence u n = 4 u n − 1 − 5 u n − 2 + 2 u n − 3 {\displaystyle 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.32 For example, the product of s n = 2 n {\displaystyle s_{n}=2^{n}} and t n = n {\displaystyle t_{n}=n} is u n = n ⋅ 2 n {\displaystyle u_{n}=n\cdot 2^{n}} ( 0 , 2 , 8 , 24 , 64 , … {\displaystyle 0,2,8,24,64,\ldots } ), which satisfies the recurrence u n = 4 u n − 1 − 4 u n − 2 {\displaystyle u_{n}=4u_{n-1}-4u_{n-2}} .

The left-shift sequence u n = s n + 1 {\displaystyle u_{n}=s_{n+1}} and the right-shift sequence u n = s n − 1 {\displaystyle u_{n}=s_{n-1}} (with u 0 = 0 {\displaystyle u_{0}=0} ) are constant-recursive because they satisfy the same recurrence relation. For example, because s n = 2 n {\displaystyle s_{n}=2^{n}} is constant-recursive, so is u n = 2 n + 1 {\displaystyle u_{n}=2^{n+1}} .

List of operations

In general, constant-recursive sequences are closed under the following operations, where s = ( s n ) n ∈ N , t = ( t n ) n ∈ N {\displaystyle s=(s_{n})_{n\in \mathbb {N} },t=(t_{n})_{n\in \mathbb {N} }} denote constant-recursive sequences, f ( x ) , g ( x ) {\displaystyle f(x),g(x)} are their generating functions, and d , e {\displaystyle d,e} are their orders, respectively.33

Operations on constant-recursive sequences
OperationDefinitionRequirementGenerating function equivalentOrder
Term-wise sum s + t {\displaystyle s+t} ( s + t ) n = s n + t n {\displaystyle (s+t)_{n}=s_{n}+t_{n}} f ( x ) + g ( x ) {\displaystyle f(x)+g(x)} ≤ d + e {\displaystyle \leq d+e} 34
Term-wise product s ⋅ t {\displaystyle s\cdot t} ( s ⋅ t ) n = s n ⋅ t n {\displaystyle (s\cdot t)_{n}=s_{n}\cdot t_{n}} 1 2 π i ∫ γ f ( ζ ) ζ g ( x ζ ) d ζ {\displaystyle {\frac {1}{2\pi i}}\int _{\gamma }{\frac {f(\zeta )}{\zeta }}g\left({\frac {x}{\zeta }}\right)\;\mathrm {d} \zeta } 3536 ≤ d ⋅ e {\displaystyle \leq d\cdot e} 3738
Cauchy product s ∗ t {\displaystyle s*t} ( s ∗ t ) n = ∑ i = 0 n s i t n − i {\displaystyle (s*t)_{n}=\sum _{i=0}^{n}s_{i}t_{n-i}} f ( x ) g ( x ) {\displaystyle f(x)g(x)} ≤ d + e {\displaystyle \leq d+e} 39
Left shift L s {\displaystyle Ls} ( L s ) n = s n + 1 {\displaystyle (Ls)_{n}=s_{n+1}} f ( x ) − s 0 x {\displaystyle {\frac {f(x)-s_{0}}{x}}} ≤ d {\displaystyle \leq d} 40
Right shift R s {\displaystyle Rs} ( R s ) n = { s n − 1 n ≥ 1 0 n = 0 {\displaystyle (Rs)_{n}={\begin{cases}s_{n-1}&n\geq 1\\0&n=0\end{cases}}} x f ( x ) {\displaystyle xf(x)} ≤ d + 1 {\displaystyle \leq d+1} 41
Cauchy inverse s ( − 1 ) {\displaystyle s^{(-1)}} ( s ( − 1 ) ) n = ∑ i 1 + ⋯ + i k = n i 1 , … , i k ≠ 0 ( − 1 ) k s i 1 s i 2 ⋯ s i k {\displaystyle (s^{(-1)})_{n}=\sum _{{i_{1}+\dots +i_{k}=n} \atop {i_{1},\ldots ,i_{k}\neq 0}}(-1)^{k}s_{i_{1}}s_{i_{2}}\cdots s_{i_{k}}} s 0 = 1 {\displaystyle s_{0}=1} 1 f ( x ) {\displaystyle {\frac {1}{f(x)}}} ≤ d + 1 {\displaystyle \leq d+1} 42
Kleene star s ( ∗ ) {\displaystyle s^{(*)}} ( s ( ∗ ) ) n = ∑ i 1 + ⋯ + i k = n i 1 , … , i k ≠ 0 s i 1 s i 2 ⋯ s i k {\displaystyle (s^{(*)})_{n}=\sum _{{i_{1}+\dots +i_{k}=n} \atop {i_{1},\ldots ,i_{k}\neq 0}}s_{i_{1}}s_{i_{2}}\cdots s_{i_{k}}} s 0 = 0 {\displaystyle s_{0}=0} 1 1 − f ( x ) {\displaystyle {\frac {1}{1-f(x)}}} ≤ d + 1 {\displaystyle \leq d+1} 43

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.44 The requirement s 0 = 1 {\displaystyle s_{0}=1} for Cauchy inverse is necessary for the case of integer sequences, but can be replaced by s 0 ≠ 0 {\displaystyle s_{0}\neq 0} if the sequence is over any field (rational, algebraic, real, or complex numbers).45

Behavior

Main articles: Skolem–Mahler–Lech theorem and Skolem problem

Unsolved problem in mathematics: Is there an algorithm to test whether a constant-recursive sequence has a zero? (more unsolved problems in mathematics)

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 {\displaystyle n} such that s n = 0 {\displaystyle s_{n}=0} . The Skolem–Mahler–Lech theorem states that the zeros of the sequence are eventually repeating: there exists constants M {\displaystyle M} and N {\displaystyle N} such that for all n > M {\displaystyle n>M} , s n = 0 {\displaystyle s_{n}=0} if and only if s n + N = 0 {\displaystyle 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.46

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 {\displaystyle s_{n}} 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.47 Given such an encoding for sequences s n {\displaystyle s_{n}} , the following problems can be studied:

Notable decision problems
ProblemDescriptionStatus4849
Existence of a zero (Skolem problem)On input ( s n ) n = 0 ∞ {\displaystyle (s_{n})_{n=0}^{\infty }} , is s n = 0 {\displaystyle s_{n}=0} for some n {\displaystyle n} ?Open
Infinitely many zerosOn input ( s n ) n = 0 ∞ {\displaystyle (s_{n})_{n=0}^{\infty }} , is s n = 0 {\displaystyle s_{n}=0} for infinitely many n {\displaystyle n} ?Decidable
Eventually all zeroOn input ( s n ) n = 0 ∞ {\displaystyle (s_{n})_{n=0}^{\infty }} , is s n = 0 {\displaystyle s_{n}=0} for all sufficiently large n {\displaystyle n} ?Decidable
PositivityOn input ( s n ) n = 0 ∞ {\displaystyle (s_{n})_{n=0}^{\infty }} , is s n > 0 {\displaystyle s_{n}>0} for all n {\displaystyle n} ?Open
Eventual positivityOn input ( s n ) n = 0 ∞ {\displaystyle (s_{n})_{n=0}^{\infty }} , is s n > 0 {\displaystyle s_{n}>0} for all sufficiently large n {\displaystyle n} ?Open

Because the square of a constant-recursive sequence s n 2 {\displaystyle 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 {\displaystyle s_{n}=c} for some n {\displaystyle n} reduces to existence-of-a-zero for the sequence s n − c {\displaystyle s_{n}-c} . As a second example, for sequences in the real numbers, weak positivity (is s n ≥ 0 {\displaystyle s_{n}\geq 0} for all n {\displaystyle n} ?) reduces to positivity of the sequence − s n {\displaystyle -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 {\displaystyle n>M} , the zeros are repeating; however, the value of M {\displaystyle M} is not known to be computable, so this does not lead to a solution to the existence-of-a-zero problem.50 On the other hand, the exact pattern which repeats after n > M {\displaystyle n>M} is computable.5152 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.535455 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.56

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). Decidability is also known for all simple rational sequences (those with simple characteristic polynomial) subject to the Skolem conjecture and the weak p-adic Schanuel conjecture.57

Degeneracy

Let r 1 , … , r n {\displaystyle r_{1},\ldots ,r_{n}} be the characteristic roots of a constant recursive sequence s {\displaystyle s} . We say that the sequence is degenerate if any ratio r i / r j {\displaystyle r_{i}/r_{j}} is a root of unity, for i ≠ j {\displaystyle i\neq j} . It is often easier to study non-degenerate sequences, in a certain sense one can reduce to this using the following theorem: if s {\displaystyle s} has order d {\displaystyle d} and is contained in a number field K {\displaystyle K} of degree k {\displaystyle k} over Q {\displaystyle \mathbb {Q} } , then there is a constant M ( k , d ) ≤ { exp ⁡ ( 2 d ( 3 log ⁡ d ) 1 / 2 ) if  k = 1 , 2 k d + 1 if  k ≥ 2 {\displaystyle 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 ≤ M ( k , d ) {\displaystyle M\leq M(k,d)} each subsequence s M n + ℓ {\displaystyle s_{Mn+\ell }} is either identically zero or non-degenerate.58

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 {\displaystyle n} rather than constants.59

A k {\displaystyle k} -regular sequence satisfies a linear recurrences with constant coefficients, but the recurrences take a different form. Rather than s n {\displaystyle s_{n}} being a linear combination of s m {\displaystyle s_{m}} for some integers m {\displaystyle m} that are close to n {\displaystyle n} , each term s n {\displaystyle s_{n}} in a k {\displaystyle k} -regular sequence is a linear combination of s m {\displaystyle s_{m}} for some integers m {\displaystyle m} whose base- k {\displaystyle k} representations are close to that of n {\displaystyle n} .60 Constant-recursive sequences can be thought of as 1 {\displaystyle 1} -regular sequences, where the base-1 representation of n {\displaystyle n} consists of n {\displaystyle n} copies of the digit 1 {\displaystyle 1} .

Notes

  • "OEIS Index Rec". OEIS index to a few thousand examples of linear recurrences, sorted by order (number of terms) and signature (vector of values of the constant coefficients)

References

  1. Kauers & Paule 2010, p. 63. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  2. Kauers & Paule 2010, p. 70. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  3. Stanley 2011, p. 464. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  4. Kauers & Paule 2010, p. 66. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  5. Halava, Vesa; Harju, Tero; Hirvensalo, Mika; Karhumäki, Juhani (2005). "Skolem's Problem – On the Border between Decidability and Undecidability". p. 1. CiteSeerX 10.1.1.155.2606. /wiki/CiteSeerX_(identifier)

  6. "Index to OEIS: Section Rec - OeisWiki". oeis.org. Retrieved 2024-04-18. https://oeis.org/wiki/Index_to_OEIS:_Section_Rec

  7. Kauers & Paule 2010, p. 70. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  8. Boyadzhiev, Boyad (2012). "Close Encounters with the Stirling Numbers of the Second Kind" (PDF). Math. Mag. 85 (4): 252–266. arXiv:1806.09468. doi:10.4169/math.mag.85.4.252. S2CID 115176876. https://www.maa.org/sites/default/files/pdf/upload_library/2/Boyadzhiev-2013.pdf

  9. Riordan, John (1964). "Inverse Relations and Combinatorial Identities". The American Mathematical Monthly. 71 (5): 485–498. doi:10.1080/00029890.1964.11992269. ISSN 0002-9890. https://www.tandfonline.com/doi/full/10.1080/00029890.1964.11992269

  10. Jordan, Charles; Jordán, Károly (1965). Calculus of Finite Differences. American Mathematical Soc. pp. 9–11. ISBN 978-0-8284-0033-6. See formula on p.9, top. 978-0-8284-0033-6

  11. Kauers & Paule 2010, p. 81. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  12. Kauers & Paule 2010, p. 70. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  13. Ouaknine, Joël; Worrell, James (2012). "Decision problems for linear recurrence sequences". Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17–19, 2012, Proceedings. Lecture Notes in Computer Science. Vol. 7550. Heidelberg: Springer-Verlag. pp. 21–28. doi:10.1007/978-3-642-33512-9_3. ISBN 978-3-642-33511-2. MR 3040104.. 978-3-642-33511-2

  14. Stanley 2011, p. 464. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  15. Stanley 2011, pp. 464–465. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  16. Martino, Ivan; Martino, Luca (2013-11-14). "On the variety of linear recurrences and numerical semigroups". Semigroup Forum. 88 (3): 569–574. arXiv:1207.0111. doi:10.1007/s00233-013-9551-2. ISSN 0037-1912. S2CID 119625519. /wiki/Semigroup_Forum

  17. Kauers & Paule 2010, p. 74. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  18. Stanley 2011, pp. 468–469. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  19. Kauers & Paule 2010, p. 67. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  20. Stanley 2011, p. 465. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  21. Kauers & Paule 2010, p. 69. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  22. Stanley 2011, p. 465. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  23. Brousseau 1971, pp. 28–34, Lesson 5. - Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association. https://www.fq.math.ca/linear.html

  24. Stanley 2011, p. 464. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  25. Kauers & Paule 2010, pp. 68–70. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  26. Brousseau 1971, p. 16, Lesson 3. - Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association. https://www.fq.math.ca/linear.html

  27. Brousseau 1971, p. 28, Lesson 5. - Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association. https://www.fq.math.ca/linear.html

  28. Greene, Daniel H.; Knuth, Donald E. (1982). "2.1.1 Constant coefficients – A) Homogeneous equations". Mathematics for the Analysis of Algorithms (2nd ed.). Birkhäuser. p. 17.. /wiki/Donald_Knuth

  29. Brousseau 1971, pp. 29–31, Lesson 5. - Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association. https://www.fq.math.ca/linear.html

  30. Kauers & Paule 2010, p. 71. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  31. Brousseau 1971, p. 37, Lesson 6. - Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association. https://www.fq.math.ca/linear.html

  32. Kauers & Paule 2010, p. 71. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  33. Stanley 2011, pp. 471. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  34. Kauers & Paule 2010, p. 71. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  35. Pohlen, Timo (2009). "The Hadamard product and universal power series" (PDF). University of Trier (Doctoral Dissertation): 36–37. https://ubt.opus.hbz-nrw.de/opus45-ubtr/frontdoor/deliver/index/docId/327/file/Dissertation.pdf

  36. See Hadamard product (series) and Parseval's theorem. /wiki/Hadamard_product_(series)

  37. Ouaknine, Joël; Worrell, James (2012). "Decision problems for linear recurrence sequences". Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17–19, 2012, Proceedings. Lecture Notes in Computer Science. Vol. 7550. Heidelberg: Springer-Verlag. pp. 21–28. doi:10.1007/978-3-642-33512-9_3. ISBN 978-3-642-33511-2. MR 3040104.. 978-3-642-33511-2

  38. Kauers & Paule 2010, p. 71. - Kauers, Manuel; Paule, Peter (2010). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6. https://books.google.com/books?id=BPeODAEACAAJ

  39. Stanley 2011, pp. 471. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  40. Stanley 2011, pp. 471. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  41. Stanley 2011, pp. 471. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  42. Stanley 2011, pp. 471. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  43. Stanley 2011, pp. 471. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  44. Stanley 2011, pp. 471. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  45. Stanley 2011, pp. 471. - Stanley, Richard P. (2011). Enumerative Combinatorics (PDF). Vol. 1 (2 ed.). Cambridge studies in advanced mathematics. https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf

  46. Lech, C. (1953). "A Note on Recurring Series". Arkiv för Matematik. 2 (5): 417–421. Bibcode:1953ArM.....2..417L. doi:10.1007/bf02590997. https://doi.org/10.1007%2Fbf02590997

  47. Ouaknine, Joël; Worrell, James (2012). "Decision problems for linear recurrence sequences". Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17–19, 2012, Proceedings. Lecture Notes in Computer Science. Vol. 7550. Heidelberg: Springer-Verlag. pp. 21–28. doi:10.1007/978-3-642-33512-9_3. ISBN 978-3-642-33511-2. MR 3040104.. 978-3-642-33511-2

  48. Ouaknine, Joël; Worrell, James (2012). "Decision problems for linear recurrence sequences". Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17–19, 2012, Proceedings. Lecture Notes in Computer Science. Vol. 7550. Heidelberg: Springer-Verlag. pp. 21–28. doi:10.1007/978-3-642-33512-9_3. ISBN 978-3-642-33511-2. MR 3040104.. 978-3-642-33511-2

  49. Lipton, Richard; Luca, Florian; Nieuwveld, Joris; Ouaknine, Joël; Purser, David; Worrell, James (2022-08-04). "On the Skolem Problem and the Skolem Conjecture". Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS '22. New York, NY, USA: Association for Computing Machinery. pp. 1–9. doi:10.1145/3531130.3533328. ISBN 978-1-4503-9351-5. 978-1-4503-9351-5

  50. Ouaknine, Joël; Worrell, James (2012). "Decision problems for linear recurrence sequences". Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17–19, 2012, Proceedings. Lecture Notes in Computer Science. Vol. 7550. Heidelberg: Springer-Verlag. pp. 21–28. doi:10.1007/978-3-642-33512-9_3. ISBN 978-3-642-33511-2. MR 3040104.. 978-3-642-33511-2

  51. Ouaknine, Joël; Worrell, James (2012). "Decision problems for linear recurrence sequences". Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17–19, 2012, Proceedings. Lecture Notes in Computer Science. Vol. 7550. Heidelberg: Springer-Verlag. pp. 21–28. doi:10.1007/978-3-642-33512-9_3. ISBN 978-3-642-33511-2. MR 3040104.. 978-3-642-33511-2

  52. Berstel, Jean; Mignotte, Maurice (1976). "Deux propriétés décidables des suites récurrentes linéaires". Bulletin de la Société Mathématique de France (in French). 104: 175–184. doi:10.24033/bsmf.1823. https://doi.org/10.24033%2Fbsmf.1823

  53. Vereshchagin, N. K. (1985-08-01). "Occurrence of zero in a linear recursive sequence". Mathematical Notes of the Academy of Sciences of the USSR. 38 (2): 609–615. doi:10.1007/BF01156238. ISSN 1573-8876. https://doi.org/10.1007/BF01156238

  54. Tijdeman, R.; Mignotte, M.; Shorey, T. N. (1984). "The distance between terms of an algebraic recurrence sequence". Journal für die reine und angewandte Mathematik. 349: 63–76. ISSN 0075-4102. https://eudml.org/doc/152622

  55. Bacik, Piotr (2024-09-02). "Completing the picture for the Skolem Problem on order-4 linear recurrence sequences". arXiv:2409.01221 [cs.FL]. /wiki/ArXiv_(identifier)

  56. Lipton, Richard; Luca, Florian; Nieuwveld, Joris; Ouaknine, Joël; Purser, David; Worrell, James (2022-08-04). "On the Skolem Problem and the Skolem Conjecture". Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS '22. New York, NY, USA: Association for Computing Machinery. pp. 1–9. doi:10.1145/3531130.3533328. ISBN 978-1-4503-9351-5. 978-1-4503-9351-5

  57. Bilu, Yuri; Luca, Florian; Nieuwveld, Joris; Ouaknine, Joël; Purser, David; Worrell, James (2022-04-28). "Skolem Meets Schanuel". arXiv:2204.13417 [cs.LO]. /wiki/ArXiv_(identifier)

  58. Everest, Graham, ed. (2003). Recurrence sequences. Mathematical surveys and monographs. Providence, RI: American Mathematical Society. p. 5. ISBN 978-0-8218-3387-2. 978-0-8218-3387-2

  59. Stanley, Richard P (1980). "Differentiably finite power series". European Journal of Combinatorics. 1 (2): 175–188. doi:10.1016/S0195-6698(80)80051-5. /wiki/Doi_(identifier)

  60. Allouche, Jean-Paul; Shallit, Jeffrey (1992). "The ring of k-regular sequences". Theoretical Computer Science. 98 (2): 163–197. doi:10.1016/0304-3975(92)90001-V. /wiki/Doi_(identifier)