Constant-recursive sequence

${\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}$.[3]

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 vector space whose dimension is finite, i.e. a finite-dimensional subspace of ${\displaystyle \mathbb {C} ^{\mathbb {N} }}$ closed under the left-shift operator. This is because the order-${\displaystyle d}$ linear recurrence relation can be understood as a proof of linear dependence between the vectors ${\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 vector space generated by ${\displaystyle (s_{n+r})_{n=0}^{\infty }}$ for all ${\displaystyle r}$.

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. 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.[4] 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).

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.

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] 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.[6] 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. 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 )}$ is constant-recursive.

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

Despite simple local dynamics, constant-recursive functions exhibit complex 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.[8]

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.[3] 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.[3] On the other hand, the exact pattern which repeats after ${\displaystyle n>M}$ is computable.[3][9] 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.[3]