Constant-recursive sequence

The sequence 0, 1, 1, 2, 3, 5, 8, 13, ... of Fibonacci numbers is constant-recursive of order 2 because it satisfies the recurrence ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$ with ${\displaystyle F_{0}=0,F_{1}=1}$. For example, ${\displaystyle F_{2}=F_{1}+F_{0}=1+0=1}$ and ${\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 ${\displaystyle L_{0}=2}$ and ${\displaystyle L_{1}=1}$. More generally, every Lucas sequence is constant-recursive of order 2.[2]

For any ${\displaystyle a}$ and any ${\displaystyle r\neq 0}$, the arithmetic progression ${\displaystyle a,a+r,a+2r,\ldots }$ is constant-recursive of order 2, because it satisfies ${\displaystyle s_{n}=2s_{n-1}-s_{n-2}}$. Generalizing this, see polynomial sequences below.

For any ${\displaystyle a\neq 0}$ and ${\displaystyle r}$, the geometric progression ${\displaystyle a,ar,ar^{2},\ldots }$ is constant-recursive of order 1, because it satisfies ${\displaystyle s_{n}=rs_{n-1}}$. This includes, for example, the sequence 1, 2, 4, 8, 16, ... as well as the rational number sequence ${\displaystyle 1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},...}$.

A sequence that is eventually periodic with period length ${\displaystyle \ell }$ is constant-recursive, since it satisfies ${\displaystyle s_{n}=s_{n-\ell }}$ for all ${\displaystyle n\geq d}$, where the order ${\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).

A sequence defined by a polynomial ${\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 ${\displaystyle d+1}$ (where ${\displaystyle d}$ is the degree of the polynomial), with coefficients given by the corresponding element of the binomial transform.[5][6] The first few such equations are

${\displaystyle s_{n}=1\cdot s_{n-1}}$ for a degree 0 (that is, constant) polynomial,

${\displaystyle s_{n}=2\cdot s_{n-1}-1\cdot s_{n-2}}$ for a degree 1 or less polynomial,

${\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

${\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.[7] Any sequence of ${\displaystyle d+1}$ integer, real, or complex values can be used as initial conditions for a constant-recursive sequence of order ${\displaystyle d+1}$. If the initial conditions lie on a polynomial of degree ${\displaystyle d-1}$ or less, then the constant-recursive sequence also obeys a lower order equation.

Let ${\displaystyle L}$ be a regular language, and let ${\displaystyle s_{n}}$ be the number of words of length ${\displaystyle n}$ in ${\displaystyle L}$. Then ${\displaystyle (s_{n})_{n=0}^{\infty }}$ is constant-recursive.[8] For example, ${\displaystyle s_{n}=2^{n}}$ for the language of all binary strings, ${\displaystyle s_{n}=1}$ for the language of all unary strings, and ${\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 ${\displaystyle \Sigma =\{a\}}$ over the semiring ${\displaystyle (\mathbb {R} ,+,\times )}$ (which is in fact a ring, and even a field) is constant-recursive.

The sequences of Jacobsthal numbers, Padovan numbers, Pell numbers, and Perrin numbers[2] are constant-recursive.

The factorial sequence ${\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 ${\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).

${\displaystyle F_{n}={\begin{bmatrix}0&1\end{bmatrix}}{\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}{\begin{bmatrix}1\\0\end{bmatrix}}.}$

Definition of the Fibonacci sequence using matrices.

A sequence ${\displaystyle (s_{n})_{n=0}^{\infty }}$ is constant-recursive of order ${\displaystyle \leq d}$ if and only if it can be written as

${\displaystyle s_{n}=uA^{n}v}$

where ${\displaystyle u}$ is a ${\displaystyle 1\times d}$ vector, ${\displaystyle A}$ is a ${\displaystyle d\times d}$ matrix, and ${\displaystyle v}$ is a ${\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, ${\displaystyle v}$ can be taken to be the first ${\displaystyle d}$ values of the sequence, ${\displaystyle A}$ the linear transformation that computes ${\displaystyle s_{n+1},s_{n+2},\ldots ,s_{n+d}}$ from ${\displaystyle s_{n},s_{n+1},\ldots ,s_{n+d-1}}$, and ${\displaystyle u}$ the vector ${\displaystyle [0,0,\ldots ,0,1]}$.[9]

Non-homogeneous	Homogeneous
${\displaystyle s_{n}=1+s_{n-1}}$	${\displaystyle s_{n}=2s_{n-1}-s_{n-2}}$
${\displaystyle s_{0}=0}$	${\displaystyle s_{0}=0;s_{1}=1}$

Definition of the sequence of natural numbers ${\displaystyle s_{n}=n}$, using a non-homogeneous recurrence and the equivalent homogeneous version.

A non-homogeneous linear recurrence is an equation of the form

${\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d}+c}$

where ${\displaystyle c}$ is an additional constant. Any sequence satisfying a non-homogeneous linear recurrence is constant-recursive. This is because subtracting the equation for ${\displaystyle s_{n-1}}$ from the equation for ${\displaystyle s_{n}}$ yields a homogeneous recurrence for ${\displaystyle s_{n}-s_{n-1}}$, from which we can solve for ${\displaystyle s_{n}}$ to obtain

${\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}}}$

${\displaystyle \sum _{n=0}^{\infty }F_{n}x^{n}={\frac {x}{1-x-x^{2}}}.}$

Definition of the Fibonacci sequence using a generating function.

A sequence is constant-recursive precisely when its generating function

${\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 ${\displaystyle {\frac {p(x)}{q(x)}}}$, where ${\displaystyle p}$ and ${\displaystyle q}$ are polynomials and ${\displaystyle q(0)\neq 0}$. 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.[10] [11]

The explicit derivation of the generating function in terms of the linear recurrence is

${\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

${\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 here must be a polynomial not divisible by ${\displaystyle x}$ (and in particular nonzero).

${\displaystyle \{(an+b)_{n=0}^{\infty }:a,b\in \mathbb {R} \}}$

2-dimensional vector space of sequences generated by the sequence ${\displaystyle s_{n}=n}$.

A sequence ${\displaystyle (s_{n})_{n=0}^{\infty }}$ is constant-recursive if and only if the set of sequences

${\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, ${\displaystyle (s_{n})_{n=0}^{\infty }}$ is contained in a finite-dimensional subspace of ${\displaystyle \mathbb {C} ^{\mathbb {N} }}$ closed under the left-shift operator.[12]

This characterization is because the order-${\displaystyle d}$ linear recurrence relation can be understood as a proof of linear dependence between the sequences ${\displaystyle (s_{n+r})_{n=0}^{\infty }}$ for ${\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 ${\displaystyle (s_{n+r})_{n=0}^{\infty }}$ for all ${\displaystyle r}$.[13]

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

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

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

Operations on constant-recursive sequences

Operation	Definition	Requirement	Generating function equivalent	Order
Term-wise sum ${\displaystyle s+t}$	${\displaystyle (s+t)_{n}=s_{n}+t_{n}}$	—	${\displaystyle f(x)+g(x)}$	${\displaystyle \leq d+e}$[16]
Term-wise product ${\displaystyle s\cdot t}$	${\displaystyle (s\cdot t)_{n}=s_{n}\cdot t_{n}}$	—	—	${\displaystyle \leq d\cdot e}$[9][16]
Cauchy product ${\displaystyle s*t}$	${\displaystyle (s*t)_{n}=\sum _{i=0}^{n}s_{i}t_{n-i}}$	—	${\displaystyle f(x)g(x)}$	${\displaystyle \leq d+e}$
Left shift ${\displaystyle Ls}$	${\displaystyle (Ls)_{n}=s_{n+1}}$	—	${\displaystyle {\frac {f(x)-s_{0}}{x}}}$	${\displaystyle \leq d}$
Right shift ${\displaystyle Rs}$	${\displaystyle (Rs)_{n}={\begin{cases}s_{n-1}&n\geq 1\\0&n=0\end{cases}}}$	—	${\displaystyle xf(x)}$	${\displaystyle \leq d+1}$
Cauchy inverse ${\displaystyle s^{(-1)}}$	${\displaystyle (s^{(-1)})_{n}=\sum _{i_{1}+\dots +i_{k}=n}(-1)^{k}s_{i_{1}}s_{i_{2}}\cdots s_{i_{k}}}$	${\displaystyle s_{0}=1}$	${\displaystyle {\frac {1}{f(x)}}}$	${\displaystyle \leq \max(2d-1,2)}$
Kleene star ${\displaystyle s^{(*)}}$	${\displaystyle (s^{(*)})_{n}=\sum _{i_{1}+\dots +i_{k}=n}s_{i_{1}}s_{i_{2}}\cdots s_{i_{k}}}$	${\displaystyle s_{0}=0}$	${\displaystyle {\frac {1}{1-f(x)}}}$	${\displaystyle \leq \max(2d-1,2)}$

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

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

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

Notable decision problems

Problem	Description	Status (2021)
Existence of a zero (Skolem problem)	On input ${\displaystyle (s_{n})_{n=0}^{\infty }}$, is ${\displaystyle s_{n}=0}$ for some ${\displaystyle n}$?	Open
Infinitely many zeros	On input ${\displaystyle (s_{n})_{n=0}^{\infty }}$, is ${\displaystyle s_{n}=0}$ for infinitely many ${\displaystyle n}$?	Decidable
Positivity	On input ${\displaystyle (s_{n})_{n=0}^{\infty }}$, is ${\displaystyle s_{n}>0}$ for all ${\displaystyle n}$?	Open
Eventual positivity	On input ${\displaystyle (s_{n})_{n=0}^{\infty }}$, is ${\displaystyle s_{n}>0}$ for all sufficiently large ${\displaystyle n}$?	Open

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