Constant-recursive sequence#Polynomial sequences

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,\; \backslash ldots$ (written as $(s\_n)\_\{n=0\}^\backslash infty$ as a shorthand) satisfying a formula of the form

$$s\_n\; =\; c\_1\; s\_\{n-1\}\; +\; c\_2\; s\_\{n-2\}\; +\; \backslash dots\; +\; c\_d\; s\_\{n-d\},$$

for all $n\; \backslash ge\; d,$ for some fixed coefficients $c\_1,\; c\_2,\; \backslash 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.

{{citation needed|date=April 2024}}

The definition above allows eventually-periodic sequences such as $1,\; 0,\; 0,\; 0,\; \backslash ldots$ and $0,\; 1,\; 0,\; 0,\; \backslash ldots$. Some authors require that $c\_d\; \backslash ne\; 0$, which excludes such sequences.{{sfn|Stanley|2011|p=464}}{{sfn|Kauers|Paule|2010|p=66}}{{cite CiteSeerX |last1=Halava|first1=Vesa|title=Skolem's Problem – On the Border between Decidability and Undecidability|date=2005|last2=Harju|first2=Tero|last3=Hirvensalo|first3=Mika|last4=Karhumäki|first4=Juhani|citeseerx=10.1.1.155.2606|page=1}}

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.{{sfn|Kauers|Paule|2010|p=70}}

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

{{citation needed|date=April 2024}}

For any $a\; \backslash ne\; 0$ and $r$, the geometric progression $a,\; a\; r,\; a\; r^2,\; \backslash 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,\; \backslash frac12,\; \backslash frac14,\; \backslash frac18,\; \backslash frac\{1\}\{16\},\; ...$.

{{citation needed|date=April 2024}}

A sequence that is eventually periodic with period length $\backslash ell$ is constant-recursive, since it satisfies $s\_n\; =\; s\_\{n-\backslash ell\}$ for all $n\; \backslash 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).

{{citation needed|date=April 2024}}

A sequence defined by a polynomial $s\_n\; =\; a\_0\; +\; a\_1\; n\; +\; a\_2\; n^2\; +\; \backslash 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.{{Cite journal|last=Boyadzhiev|first=Boyad|date=2012|title=Close Encounters with the Stirling Numbers of the Second Kind|url=https://www.maa.org/sites/default/files/pdf/upload_library/2/Boyadzhiev-2013.pdf|journal=Math. Mag.|volume=85|issue=4|pages=252–266|doi=10.4169/math.mag.85.4.252|arxiv=1806.09468|s2cid=115176876}}{{Cite journal |last=Riordan |first=John |date=1964 |title=Inverse Relations and Combinatorial Identities |url=https://www.tandfonline.com/doi/full/10.1080/00029890.1964.11992269 |journal=The American Mathematical Monthly |language=en |volume=71 |issue=5 |pages=485–498 |doi=10.1080/00029890.1964.11992269 |issn=0002-9890}} The first few such equations are

: $s\_n\; =\; 1\; \backslash cdot\; s\_\{n-1\}$ for a degree 0 (that is, constant) polynomial,

: $s\_n\; =\; 2\backslash cdot\; s\_\{n-1\}\; -\; 1\backslash cdot\; s\_\{n-2\}$ for a degree 1 or less polynomial,

: $s\_n\; =\; 3\backslash cdot\; s\_\{n-1\}\; -\; 3\backslash cdot\; s\_\{n-2\}\; +\; 1\backslash cdot\; s\_\{n-3\}$ for a degree 2 or less polynomial, and

: $s\_n\; =\; 4\backslash cdot\; s\_\{n-1\}\; -\; 6\backslash cdot\; s\_\{n-2\}\; +\; 4\backslash cdot\; s\_\{n-3\}\; -\; 1\backslash 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.{{Cite book|last1=Jordan|first1=Charles|url=https://books.google.com/books?id=3RfZOsDAyQsC&dq=theory+of+finite+differences&pg=PA1|title=Calculus of Finite Differences|last2=Jordán|first2=Károly|date=1965|publisher=American Mathematical Soc.|isbn=978-0-8284-0033-6|language=en|pages=9–11}} See formula on p.9, top.

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.

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\}^\backslash infty$ is constant-recursive.{{sfn|Kauers|Paule|2010|p=81}} 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 $\backslash Sigma\; =\; \backslash \{a\backslash \}$ over the semiring $(\backslash mathbb\{R\},\; +,\; \backslash times)$ (which is in fact a ring, and even a field) is constant-recursive.

{{citation needed|date=April 2024}}

The sequences of Jacobsthal numbers, Padovan numbers, Pell numbers, and Perrin numbers{{sfn|Kauers|Paule|2010|p=70}} are constant-recursive.

The factorial sequence $1,\; 1,\; 2,\; 6,\; 24,\; 120,\; 720,\; \backslash 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,\; \backslash ldots$ is not constant-recursive. This is because the generating function of the Catalan numbers is not a rational function (see #Equivalent definitions).

{{main|Companion matrix}}

{{float begin|width=195px|side=right}}

|-style="text-align:center;"

|

\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^n

\begin{bmatrix}1 \\ 0\end{bmatrix}.

{{float end|Definition of the Fibonacci sequence using matrices.}}

A sequence $(s\_n)\_\{n=0\}^\backslash 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\; \backslash times\; d$ vector, $A$ is a $d\; \backslash times\; d$ matrix, and $v$ is a $d\; \backslash 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\},\; \backslash ldots,\; s\_\{n+d\}$ from $s\_n,\; s\_\{n+1\},\; \backslash ldots,\; s\_\{n+d-1\}$, and $u$ the vector $[0,\; 0,\; \backslash ldots,\; 0,\; 1]$.

{{main|Linear recurrence with constant coefficients#Conversion to homogeneous form}}

{{float begin|width=250px|side=right}}

|- class="wikitable"

! Non-homogeneous !! Homogeneous

|- align = "center"

| $s\_n\; =\; 1\; +\; s\_\{n-1\}$

| $s\_n\; =\; 2s\_\{n-1\}\; -\; s\_\{n-2\}$

|- align = "center"

| $s\_0\; =\; 0$

| $s\_0\; =\; 0;\; s\_1\; =\; 1$

{{float end|Definition of the sequence of natural numbers $s\_n\; =\; n$, using a non-homogeneous recurrence and the equivalent homogeneous version.}}

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

:$s\_n\; =\; c\_1\; s\_\{n-1\}\; +\; c\_2\; s\_\{n-2\}\; +\; \backslash dots\; +\; c\_d\; s\_\{n-d\}\; +\; c$

where $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\}$ from the equation for $s\_n$ yields a homogeneous recurrence for $s\_n\; -\; s\_\{n-1\}$, from which we can solve for $s\_n$ to obtain{{citation needed|date=April 2024}}

:

{{float begin|width=180px|side=right}}

|-style="text-align:center;"

|$\backslash sum\_\{n\; =\; 0\}^\backslash infty\; F\_n\; x^n\; =\; \backslash frac\{x\}\{1-x-x^2\}.$

{{float end|caption=Definition of the Fibonacci sequence using a generating function.}}

A sequence is constant-recursive precisely when its generating function

:$\backslash sum\_\{n\; =\; 0\}^\backslash infty\; s\_n\; x^n\; =\; s\_0\; +\; s\_1\; x^1\; +\; s\_2\; x^2\; +\; s\_3\; x^3\; +\; \backslash cdots$

is a rational function $p(x)\; \backslash ,/\backslash ,\; q(x)$, where $p$ and $q$ are polynomials and $q(0)\; =\; 1$.{{sfn|Stanley|2011|p=464}}

Moreover, the order of the sequence is the minimum $d$ such that it has such a form with $\backslash text\{deg\; \}\; q(x)\; \backslash le\; d$ and .{{sfn|Stanley|2011|pp=464-465}}

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:{{Cite journal|title = On the variety of linear recurrences and numerical semigroups|journal = Semigroup Forum|date = 2013-11-14|issn = 0037-1912|pages = 569–574|volume = 88|issue = 3|doi = 10.1007/s00233-013-9551-2|language = en|first1 = Ivan|last1 = Martino|first2 = Luca|last2 = Martino|arxiv = 1207.0111|s2cid = 119625519}}{{sfn|Kauers|Paule|2010|p=74}}

:$\backslash sum\_\{n\; =\; 0\}^\backslash infty\; s\_n\; x^n\; =\; \backslash frac\{b\_0\; +\; b\_1\; x^1\; +\; b\_2\; x^2\; +\; \backslash dots\; +\; b\_\{d-1\}\; x^\{d-1\}\}\{1\; -\; c\_1\; x^1\; -\; c\_2\; x^2\; -\; \backslash dots\; -\; c\_d\; x^d\},$

where

:$b\_n\; =\; s\_n\; -\; c\_1\; s\_\{n-1\}\; -\; c\_2\; s\_\{n-2\}\; -\; \backslash dots\; -\; c\_d\; s\_\{n-d\}.${{sfn|Stanley|2011|pp=468-469}}

It follows from the above that the denominator $q(x)$ must be a polynomial not divisible by $x$ (and in particular nonzero).

{{float begin|width=175px|side=right}}

|-align=center

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

{{float end|2-dimensional vector space of sequences generated by the sequence $s\_n\; =\; n$.}}

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

:$\backslash left\backslash \{(s\_\{n+r\})\_\{n=0\}^\backslash infty\; :\; r\; \backslash geq\; 0\backslash right\backslash \}$

is contained in a sequence space (vector space of sequences) whose dimension is finite. That is, $(s\_n)\_\{n=0\}^\backslash infty$ is contained in a finite-dimensional subspace of $\backslash mathbb\{C\}^\backslash mathbb\{N\}$ closed under the left-shift operator.{{sfn|Kauers|Paule|2010|p=67}}{{sfn|Stanley|2011|p=465}}

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\}^\backslash infty$ for $r=0,\; \backslash 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\}^\backslash infty$ for all $r$.{{sfn|Kauers|Paule|2010|p=69}}{{sfn|Stanley|2011|p=465}}

{{for|a derivation of the closed form|Linear recurrence with constant coefficients#General solution}}

{{float_begin|side=right|width=300px}}

|-align=center

|$F\_n\; =\; \backslash frac\{1\}\{\backslash sqrt\{5\}\}(1.618\backslash ldots)^n\; -\; \backslash frac\{1\}\{\backslash sqrt\{5\}\}(-0.618\backslash ldots)^n$

{{float_end|Closed-form characterization of the Fibonacci sequence (Binet's formula)}}

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\; +\; \backslash cdots\; +\; k\_e(n)\; r\_e^n,$

for all $n\; \backslash ge\; 0$, where

• The term $z\_n$ is a sequence which is zero for all $n\; \backslash ge\; d$ (where $d$ is the order of the sequence);
• The terms $k\_1(n),\; k\_2(n),\; \backslash ldots,\; k\_e(n)$ are complex polynomials; and
• The terms $r\_1,\; r\_2,\; \backslash ldots,\; r\_k$ are distinct complex constants.{{sfn|Brousseau|1971|pp=28-34|loc=Lesson 5}}{{sfn|Stanley|2011|p=464}}

This characterization is exact: every sequence of complex numbers that can be written in the above form is constant-recursive.{{sfn|Kauers|Paule|2010|pp=68-70}}

For example, the Fibonacci number $F\_n$ is written in this form using Binet's formula:{{sfn|Brousseau|1971|p=16|loc=Lesson 3}}

:$F\_n\; =\; \backslash frac\{1\}\{\backslash sqrt\{5\}\}\backslash varphi^n\; -\; \backslash frac\{1\}\{\backslash sqrt\{5\}\}\backslash psi^n,$

where $\backslash varphi\; =\; (1\; +\; \backslash sqrt\{5\})\; \backslash ,/\backslash ,\; 2\; \backslash approx\; 1.61803\backslash ldots$ is the golden ratio and $\backslash psi\; =\; -1\; \backslash ,/\backslash ,\; \backslash 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\; \backslash ,/\backslash ,\; \backslash sqrt\{5\}$ are both constant polynomials, $r\_1\; =\; \backslash varphi$, and $r\_2\; =\; \backslash psi$.

The term $z\_n$ is only needed when $c\_d\backslash 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\; \backslash ge\; d$.{{citation needed|date=April 2024}}

The complex numbers $r\_1,\; \backslash ldots,\; r\_n$ are the roots of the characteristic polynomial of the recurrence:

:$x^d\; -\; c\_1\; x^\{d-1\}\; -\; \backslash dots\; -\; c\_\{d-1\}\; x\; -\; c\_d$

whose coefficients are the same as those of the recurrence.{{sfn|Brousseau|1971|p=28|loc=Lesson 5}}

We call $r\_1,\; \backslash 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,\; \backslash 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 $n$th term is of the form $s\_n\; =\; (a\; +\; b\; n\; +\; c\; n^2)\; r^n.${{cite book |chapter=2.1.1 Constant coefficients – A) Homogeneous equations|title=Mathematics for the Analysis of Algorithms|first1=Daniel H.|last1=Greene|first2=Donald E.|last2=Knuth|author2-link=Donald Knuth| edition=2nd| publisher=Birkhäuser |page=17 | year=1982}}.{{sfn|Brousseau|1971|pp=29-31|loc=Lesson 5}}

The sum of two constant-recursive sequences is also constant-recursive.{{sfn|Kauers|Paule|2010|p=71}}{{sfn|Brousseau|1971|p=37|loc=Lesson 6}} For example, the sum of $s\_n\; =\; 2^n$ and $t\_n\; =\; n$ is $u\_n\; =\; 2^n\; +\; n$ ($1,\; 3,\; 6,\; 11,\; 20,\; \backslash 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.{{sfn|Kauers|Paule|2010|p=71}} For example, the product of $s\_n\; =\; 2^n$ and $t\_n\; =\; n$ is $u\_n\; =\; n\; \backslash cdot\; 2^n$ ($0,\; 2,\; 8,\; 24,\; 64,\; \backslash 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\}$.

In general, constant-recursive sequences are closed under the following operations, where $s\; =\; (s\_n)\_\{n\; \backslash in\; \backslash mathbb\{N\}\},\; t\; =\; (t\_n)\_\{n\; \backslash in\; \backslash mathbb\{N\}\}$ denote constant-recursive sequences, $f(x),\; g(x)$ are their generating functions, and $d,\; e$ are their orders, respectively.{{sfn|Stanley|2011|pp=471}}

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.{{sfn|Stanley|2011|pp=471}} The requirement $s\_0\; =\; 1$ for Cauchy inverse is necessary for the case of integer sequences, but can be replaced by $s\_0\; \backslash ne\; 0$ if the sequence is over any field (rational, algebraic, real, or complex numbers).{{sfn|Stanley|2011|pp=471}}

{{main|Skolem–Mahler–Lech theorem|Skolem problem}}

{{Unsolved|mathematics|Is there an algorithm to test whether a constant-recursive sequence has a zero?}}

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.{{cite journal|last=Lech|first=C.|title=A Note on Recurring Series|journal=Arkiv för Matematik|volume=2|pages=417–421|year=1953|issue=5|doi=10.1007/bf02590997|bibcode=1953ArM.....2..417L |doi-access=free}}

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 or rational numbers, or even over the algebraic numbers.{{cite book

| last1 = Ouaknine | first1 = Joël

| last2 = Worrell | first2 = James

| chapter = Decision problems for linear recurrence sequences

| doi = 10.1007/978-3-642-33512-9_3

| mr = 3040104

| pages = 21–28

| publisher = Springer-Verlag | location = Heidelberg

| series = Lecture Notes in Computer Science

| title = Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17–19, 2012, Proceedings

| volume = 7550

| year = 2012| isbn = 978-3-642-33511-2

}}.

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\; \backslash 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. On the other hand, the exact pattern which repeats after $n\; >\; M$ is computable.{{Cite journal|last1=Berstel|first1=Jean|last2=Mignotte|first2=Maurice|date=1976|title=Deux propriétés décidables des suites récurrentes linéaires|journal=Bulletin de la Société Mathématique de France|language=fr|volume=104|pages=175–184|doi=10.24033/bsmf.1823|doi-access=free}} 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.{{Cite journal |last=Vereshchagin |first=N. K. |date=1985-08-01 |title=Occurrence of zero in a linear recursive sequence |url=https://doi.org/10.1007/BF01156238 |journal=Mathematical Notes of the Academy of Sciences of the USSR |language=en |volume=38 |issue=2 |pages=609–615 |doi=10.1007/BF01156238 |issn=1573-8876}}{{Cite journal |last1=Tijdeman |first1=R. |last2=Mignotte |first2=M. |last3=Shorey |first3=T. N. |date=1984 |title=The distance between terms of an algebraic recurrence sequence. |url=https://eudml.org/doc/152622 |journal=Journal für die reine und angewandte Mathematik |volume=349 |pages=63–76 |issn=0075-4102}}{{cite arXiv |last=Bacik |first=Piotr |title=Completing the picture for the Skolem Problem on order-4 linear recurrence sequences |date=2024-09-02 |class=cs.FL |eprint=2409.01221}} 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.

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.{{cite arXiv |last1=Bilu |first1=Yuri |title=Skolem Meets Schanuel |date=2022-04-28 |eprint=2204.13417 |last2=Luca |first2=Florian |last3=Nieuwveld |first3=Joris |last4=Ouaknine |first4=Joël |last5=Purser |first5=David |last6=Worrell |first6=James|class=cs.LO }}

Let $r\_1,\; \backslash ldots,\; r\_n$ be the characteristic roots of a constant recursive sequence $s$. We say that the sequence is degenerate if any ratio $r\_i/r\_j$ is a root of unity, for $i\; \backslash 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$ has order $d$ and is contained in a number field $K$ of degree $k$ over $\backslash mathbb\; Q$, then there is a constant

such that for some $M\; \backslash leq\; M(k,d)$ each subsequence $s\_\{Mn+\backslash ell\}$ is either identically zero or non-degenerate.{{Cite book |title=Recurrence sequences |date=2003 |publisher=American Mathematical Society |isbn=978-0-8218-3387-2 |editor-last=Everest |editor-first=Graham |series=Mathematical surveys and monographs |location=Providence, RI |pages=5}}

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.{{Cite journal |last=Stanley |first=Richard P |date=1980 |title=Differentiably finite power series |journal=European Journal of Combinatorics |volume=1 |issue=2 |pages=175–188|doi=10.1016/S0195-6698(80)80051-5 }}

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$.{{Cite journal |last1=Allouche |first1=Jean-Paul |last2=Shallit |first2=Jeffrey |date=1992 |title=The ring of k-regular sequences |journal=Theoretical Computer Science |volume=98 |issue=2 |pages=163–197|doi=10.1016/0304-3975(92)90001-V }} 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$.

{{citation needed|date=April 2024}}

{{reflist}}

{{refbegin}}

• {{cite book |last=Brousseau |first=Alfred |title=Linear Recursion and Fibonacci Sequences |year=1971 |publisher=Fibonacci Association |url=https://www.fq.math.ca/linear.html }}
• {{Cite book |last1=Kauers |first1=Manuel |last2=Paule |first2=Peter |title=The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates |url=https://books.google.com/books?id=BPeODAEACAAJ |date=2010 |publisher=Springer Vienna |isbn=978-3-7091-0444-6 |language=en |pages=66 }}
• {{cite book |last=Stanley |first=Richard P. |date=2011 |title=Enumerative Combinatorics |url=https://www.ms.uky.edu/~sohum/putnam/enu_comb_stanley.pdf |volume=1 |edition=2 |publisher=Cambridge studies in advanced mathematics}}

{{refend}}

• {{cite web |title= OEIS Index Rec|url=http://oeis.org/wiki/Index_to_OEIS:_Section_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)

Category:Combinatorics

Category:Dynamical systems

Category:Integer sequences

Category:Linear algebra

Category:Recurrence relations