View source for Constant-recursive sequence

{{short description|Infinite sequence of numbers satisfying a linear equation}}
[[File:Fibonacci sequence.jpg|thumb|350px|right|The Fibonacci sequence is constant-recursive: each element of the sequence is the sum of the previous two.]]
[[File:Constant-recursive-sequences.svg|thumb|350px|right|[[Hasse diagram|Hasse diagram]] of some subclasses of constant-recursive sequences, ordered by inclusion]]
{{Unsolved|mathematics|Is there an algorithm to test whether a constant-recursive sequence has a zero?}}

In [[Mathematics|mathematics]] and [[Theoretical computer science|theoretical computer science]], a '''constant-recursive sequence''' is an [[Sequence|infinite sequence]] of [[Number|number]]s in which each number in the sequence is equal to a fixed [[Linear combination|linear combination]] of one or more of its immediate predecessors. The concept is variously known as a '''linear recurrence sequence''', '''linear-recursive sequence''', '''linear-recurrent sequence''', a '''C-finite sequence''',{{sfn|Kauers|Paule|2010|p=63}} or a solution to a [[Linear recurrence with constant coefficients|linear recurrence with constant coefficients]].

A prototypical example is the [[Fibonacci sequence]] <math>0, 1, 1, 2, 3, 5, 8, 13, \ldots</math>, in which each number is the sum of the previous two.{{sfn|Kauers|Paule|2010|p=70}} The [[Power of two|power of two]] sequence <math>1, 2, 4, 8, 16, \ldots</math> is also constant-recursive because each number is the sum of twice the previous number. The [[Square number|square number]] sequence <math>0, 1, 4, 9, 16, 25, \ldots</math> is also constant-recursive. However, not all sequences are constant-recursive; for example, the [[Factorial|factorial]] sequence <math>1, 1, 2, 6, 24, 120, \ldots</math> is not constant-recursive. All [[Arithmetic progression|arithmetic progression]]s, all [[Geometric progression|geometric progression]]s, and all [[Polynomial|polynomial]]s are constant-recursive.

Formally, a sequence of numbers <math>s_0, s_1, s_2, s_3, \ldots</math> is constant-recursive if it satisfies a [[Recurrence relation|recurrence relation]]
:<math display=block>s_n = c_1 s_{n-1} + c_2 s_{n-2} + \dots + c_d s_{n-d},</math>
where <math>c_i</math> are [[Constant (mathematics)|constant]]s. For example, the Fibonacci sequence satisfies the recurrence relation <math>F_n = F_{n-1} + F_{n-2},</math> where <math>F_n</math> is the <math>n</math>th Fibonacci number.

Constant-recursive sequences are studied in [[Combinatorics|combinatorics]] and the theory of [[Finite difference|finite difference]]s. They also arise in [[Algebraic number theory|algebraic number theory]], due to the relation of the sequence to polynomial roots; in the [[Analysis of algorithms|analysis of algorithms]], as the running time of simple [[Recursion (computer science)|recursive function]]s; and in the theory of [[Formal language|formal language]]s, where they count strings up to a given length in a [[Regular language|regular language]]. Constant-recursive sequences are [[Closure (mathematics)|closed]] under important mathematical operations such as [[Pointwise|term-wise]] [[Addition|addition]], term-wise [[Multiplication|multiplication]], and [[Cauchy product]].

The [[Skolem–Mahler–Lech theorem]] states that the [[Zero of a function|zeros]] of a constant-recursive sequence have a regularly repeating (eventually periodic) form. On the other hand, the [[Skolem problem]], which asks for an [[Algorithm|algorithm]] to determine whether a linear recurrence has at least one zero, remains [[List of unsolved problems in mathematics|unsolved]].

==Definition==

A '''constant-recursive sequence''' is any sequence of [[Integer|integer]]s, [[Rational number|rational number]]s, [[Algebraic number|algebraic number]]s, [[Real number|real number]]s, or [[Complex number|complex number]]s <math>s_0, s_1, s_2, s_3, \ldots</math> (written as <math>(s_n)_{n=0}^\infty</math> as a shorthand) satisfying a formula of the form

:<math display=block>s_n = c_1 s_{n-1} + c_2 s_{n-2} + \dots + c_d s_{n-d},</math>

for all <math>n \ge d,</math> where <math>c_i</math> are constants.
(This equation is called a [[Linear recurrence with constant coefficients|linear recurrence with constant coefficients]] of order ''d''.)
The '''order''' of the constant-recursive sequence is the smallest <math>d \ge 1</math> such that the sequence satisfies a formula of the above form, or <math>d = 0</math> for the everywhere-zero sequence.

The ''d'' [[Coefficient|coefficient]]s <math>c_1, c_2, \dots, c_d</math> must be coefficients ranging over the same domain as the sequence (integers, rational numbers, algebraic numbers, real numbers, or complex numbers). For example for a rational constant-recursive sequence, <math>s_i</math> and <math>c_i</math> must be rational numbers.

The definition above allows eventually-[[Periodic sequence|periodic]] sequences such as <math>1, 0, 0, 0, \ldots</math> and <math>0, 1, 0, 0, \ldots</math>. Some authors require that <math>c_d \ne 0</math>, which excludes such sequences.<ref name=Border>{{Citation|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}}</ref>{{sfn|Kauers|Paule|2010|p=66}}

==Examples==

{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|+ Selected examples of integer constant-recursive sequences
! Name !! Order (<math>d</math>&hairsp;&hairsp;) !! First few values !! Recurrence (for <math>n \ge d</math>&hairsp;) !! [[Generating function]] !! OEIS
|-
| Zero sequence || 0 || 0, 0, 0, 0, 0, 0, ... || <math>s_n = 0</math> || <math>\frac{0}{1}</math> || {{OEIS link|A000004}}
|-
| One sequence || 1 || 1, 1, 1, 1, 1, 1, ... || <math>s_n = s_{n-1}</math> || <math>\frac{1}{1-x}</math> || {{OEIS link|A000012}}
|-
| [[Indicator function|Characteristic function]] of <math>\{0\}</math> || 1 || 1, 0, 0, 0, 0, 0,  ... || <math>s_n = 0</math> || <math>\frac{1}{1}</math> || {{OEIS link|A000007}}
|-
| Powers of two || 1 || 1, 2, 4, 8, 16, 32, ... || <math>s_n = 2 s_{n-1}</math> || <math>\frac{1}{1-2x}</math> || {{OEIS link|A000079}}
|-
| Powers of −1|| 1 || 1, −1, 1, −1, 1, −1, ... || <math>s_n = -s_{n-1}</math> || <math>\frac{1}{1+x}</math> || {{OEIS link|A033999}}
|-
| Characteristic function of <math>\{1\}</math> || 2 || 0, 1, 0, 0, 0, 0, ... || <math>s_n = 0</math> || <math>\frac{x}{1}</math> || {{OEIS link|A063524}}
|-
| [[Decimal representation|Decimal expansion]] of 1/6 || 2 || 1, 6, 6, 6, 6, 6, ... || <math>s_n = s_{n-1}</math> || <math>\frac{1 + 5x}{1 - x}</math> || {{OEIS link|A020793}}
|-
| Decimal expansion of 1/11 || 2 || 0, 9, 0, 9, 0, 9, ... || <math>s_n = s_{n-2}</math> || <math>\frac{9x}{1-x^2}</math> || {{OEIS link|A010680}}
|-
| [[Natural number|Nonnegative integers]] || 2 || 0, 1, 2, 3, 4, 5, ... || <math>s_n = 2s_{n-1} - s_{n-2}</math> || <math>\frac{x}{(1-x)^2}</math> || {{OEIS link|A001477}}
|-
| [[Parity (mathematics)|Odd]] positive integers || 2 || 1, 3, 5, 7, 9, 11, ... || <math>s_n = 2s_{n-1} - s_{n-2}</math> || <math>\frac{1+x}{(1-x)^2}</math> || {{OEIS link|A005408}}
|-
| [[Fibonacci number]]s || 2 || 0, 1, 1, 2, 3, 5, 8, 13, ... || <math>s_n = s_{n-1} + s_{n-2}</math> || <math>\frac{x}{1-x-x^2}</math> || {{OEIS link|A000045}}
|-
| [[Lucas number]]s || 2 || 2, 1, 3, 4, 7, 11, 18, 29, ... || <math>s_n = s_{n-1} + s_{n-2}</math> || <math>\frac{2-x}{1-x-x^2}</math> || {{OEIS link|A000032}}
|-
| [[Pell number]]s || 2 || 0, 1, 2, 5, 12, 29, 70, ... || <math>s_n = 2s_{n-1} + s_{n-2}</math> || <math>\frac{x}{1-2x-x^2}</math> || {{OEIS link|A000129}}
|-
| Powers of two [[Interleave sequence|interleaved with]] 0s || 2 || 1, 0, 2, 0, 4, 0, 8, 0, ... || <math>s_n = 2 s_{n-2}</math> || <math>\frac{1}{1-2x^2}</math> || {{OEIS link|A077957}}
|-
| Inverse of 6th [[Cyclotomic polynomial|cyclotomic polynomial]] || 2 || 1, 1, 0, −1, −1, 0, 1, 1, ... || <math>s_n = s_{n-1} - s_{n-2}</math> || <math>\frac{1}{1-x+x^2}</math> || {{OEIS link|A010892}}
|-
| [[Triangular number]]s || 3 || 0, 1, 3, 6, 10, 15, 21, ... || <math>s_n = 3s_{n-1} - 3s_{n-2} + s_{n-3}</math> || <math>\frac{x}{(1-x)^3}</math> || {{OEIS link|A000217}}
|}

===Fibonacci and Lucas sequences===
The sequence 0, 1, 1, 2, 3, 5, 8, 13, ... of [[Fibonacci number]]s is constant-recursive of order 2 because it satisfies the recurrence <math>F_n = F_{n-1} + F_{n-2}</math> with <math>F_0 = 0, F_1 = 1</math>. For example, <math>F_2 = F_1 + F_0 = 1 + 0 = 1</math> and <math>F_6 = F_5 + F_4 = 5 + 3 = 8</math>. The sequence 2, 1, 3, 4, 7, 11, ... of [[Lucas number]]s satisfies the same recurrence as the Fibonacci sequence but with initial conditions <math>L_0 = 2</math> and <math>L_1 = 1</math>. More generally, every [[Lucas sequence]] is constant-recursive of order 2.{{sfn|Kauers|Paule|2010|p=70}}

===Arithmetic progressions===
For any <math>a</math> and any <math>r \ne 0</math>, the [[Arithmetic progression|arithmetic progression]] <math>a, a+r, a+2r, \ldots</math> is constant-recursive of order 2, because it satisfies <math>s_n = 2s_{n-1} - s_{n-2}</math>. Generalizing this, see [[Constant-recursive sequence#Polynomial sequences|polynomial sequences]] below.

===Geometric progressions===
For any <math>a \ne 0</math> and <math>r</math>, the [[Geometric progression|geometric progression]] <math>a, a r, a r^2, \ldots</math> is constant-recursive of order 1, because it satisfies <math>s_n = r s_{n-1}</math>. This includes, for example, the sequence 1, 2, 4, 8, 16, ... as well as the rational number sequence <math>1, \frac12, \frac14, \frac18, \frac{1}{16}, ...</math>.

===Eventually periodic sequences===
A sequence that is eventually periodic with period length <math>\ell</math> is constant-recursive, since it satisfies <math>s_n = s_{n-\ell}</math> for all <math>n \geq d</math>, where the order <math>d</math> 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 <math>s_n = a_0 + a_1 n + a_2 n^2 + \cdots + a_d n^d</math> is constant-recursive. The sequence satisfies a recurrence of order <math>d + 1</math> (where <math>d</math> is the [[Degree of a polynomial|degree]] of the polynomial), with coefficients given by the corresponding element of the [[Binomial transform|binomial transform]].<ref>{{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}}</ref><ref>{{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}}</ref> The first few such equations are

: <math>s_n = 1 \cdot s_{n-1}</math> for a degree 0 (that is, constant) polynomial,
: <math>s_n = 2\cdot s_{n-1} - 1\cdot s_{n-2}</math> for a degree 1 or less polynomial,
: <math>s_n = 3\cdot s_{n-1} - 3\cdot s_{n-2} + 1\cdot s_{n-3}</math> for a degree 2 or less polynomial, and
: <math>s_n = 4\cdot s_{n-1} - 6\cdot s_{n-2} + 4\cdot s_{n-3} - 1\cdot s_{n-4}</math> for a degree 3 or less polynomial.

A sequence obeying the order-''d'' equation also obeys all higher order equations. These identities may be [[Mathematical proof|proved]] in a number of ways, including via the theory of [[Finite difference|finite difference]]s.<ref>{{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.</ref>
Any sequence of <math>d + 1</math> integer, real, or complex values can be used as initial conditions for a constant-recursive sequence of order <math>d + 1</math>. If the initial conditions lie on a polynomial of degree <math>d - 1</math> or less, then the constant-recursive sequence also obeys a lower order equation.

===Enumeration of words in a regular language===

Let <math>L</math> be a [[Regular language|regular language]], and let <math>s_n</math> be the number of words of length <math>n</math> in <math>L</math>. Then <math>(s_n)_{n=0}^\infty</math> is constant-recursive.{{sfn|Kauers|Paule|2010|p=81}} For example, <math>s_n = 2^n</math> for the language of all binary strings, <math>s_n = 1</math> for the language of all unary strings, and <math>s_n = F_{n+2}</math> for the language of all binary strings that do not have two consecutive ones. More generally, any function accepted by a [[Weighted automaton|weighted automaton]] over the unary alphabet <math>\Sigma = \{a\}</math> over the [[Semiring|semiring]] <math>(\mathbb{R}, +, \times)</math> (which is in fact a [[Ring (mathematics)|ring]], and even a [[Field (mathematics)|field]]) is constant-recursive.

===Other examples===

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

===Non-examples===

The [[Factorial|factorial]] sequence <math>1, 1, 2, 6, 24, 120, 720, \ldots</math> is not constant-recursive. More generally, every constant-recursive function is asymptotically bounded by an [[Exponential function|exponential function]] (see #Closed-form characterization) and the factorial sequence grows faster than this.

The Catalan sequence <math>1, 1, 2, 5, 14, 42, 132, \ldots</math> is not constant-recursive. This is because the [[Catalan number#First proof|generating function of the Catalan numbers]] is not a [[Rational function|rational function]] (see #Equivalent definitions).

==Equivalent definitions==

===In terms of matrices===

{{main|Companion matrix}}
{{float_begin|side=right|width=225px}}
|-align=center
|<math>F_n = \begin{bmatrix}0 & 1\end{bmatrix}
\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^n
\begin{bmatrix}1 \\ 0\end{bmatrix}.</math>
{{float_end|Definition of the Fibonacci sequence using matrices.}}

A sequence <math>(s_n)_{n=0}^\infty</math> is constant-recursive of order <math>\le d</math> if and only if it can be written as
:<math>s_n = u A^n v</math>
where <math>u</math> is a <math>1 \times d</math> vector, <math>A</math> is a <math>d \times d</math> [[Matrix (mathematics)|matrix]], and <math>v</math> is a <math>d \times 1</math> vector, where the elements come from the same domain (integers, rational numbers, algebraic numbers, real numbers, or complex numbers) as the original sequence. Specifically, <math>v</math> can be taken to be the first <math>d</math> values of the sequence, <math>A</math> the linear transformation that computes <math>s_{n+1}, s_{n+2}, \ldots, s_{n+d}</math> from <math>s_n, s_{n+1}, \ldots, s_{n+d-1}</math>, and <math>u</math> the vector <math>[0, 0, \ldots, 0, 1]</math>.<ref name="ow"/>

===In terms of non-homogeneous linear recurrences===

{{float_begin|width=350px}}
|- class="wikitable"
! Non-homogeneous !! Homogeneous
|- align = "center"
| <math>s_n = 1 + s_{n-1}</math>
| <math>s_n = 2s_{n-1} - s_{n-2}</math>
|- align = "center"
| <math>s_0 = 0</math>
| <math>s_0 = 0; s_1 = 1</math>
{{float_end|Definition of the sequence of [[Natural number|natural number]]s <math>s_n = n</math>, using a non-homogeneous recurrence and the equivalent homogeneous version.}}

A '''non-homogeneous linear recurrence''' is an equation of the form
:<math>s_n = c_1 s_{n-1} + c_2 s_{n-2} + \dots + c_d s_{n-d} + c</math>
where <math>c</math> is an additional constant. Any sequence satisfying a non-homogeneous linear recurrence is constant-recursive. This is because subtracting the equation for <math>s_{n-1}</math> from the equation for <math>s_n</math> yields a homogeneous recurrence for <math>s_n - s_{n-1}</math>, from which we can solve for <math>s_n</math> to obtain
:<math>\begin{align}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{align}</math>

=== In terms of generating functions ===

{{float_begin|side=right|width=200px}}
|-align=center
|<math>\sum_{n = 0}^\infty F_n x^n = \frac{x}{1-x-x^2}.</math>
{{float_end|Definition of the Fibonacci sequence using a generating function.}}

A sequence is constant-recursive precisely when its [[Generating function|generating function]]
:<math>\sum_{n = 0}^\infty s_n x^n = s_0 + s_1 x^1 + s_2 x^2 + s_3 x^3 + \cdots</math>
is a rational function <math>\frac{p(x)}{q(x)}</math>, where <math>p</math> and <math>q</math> are polynomials and <math>q(0) \ne 0</math>. The denominator is the polynomial obtained from the auxiliary polynomial by [[Reciprocal polynomial|reversing the order of the coefficients]], and the numerator is determined by the initial values of the sequence.<ref>{{Cite journal|title = On the variety of linear recurrences and numerical semigroups|journal = [[Organization:Semigroup Forum|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}}</ref>
{{sfn|Kauers|Paule|2010|p=74}}

The explicit derivation of the generating function in terms of the linear recurrence is
:<math>\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},
</math>
where
:<math>b_n = s_n - c_1 s_{n-1} - c_2 s_{n-2} - \dots - c_d s_{n-d}.</math>
It follows from the above that the denominator here must be a polynomial not divisible by <math>x</math> (and in particular nonzero).

===In terms of sequence spaces===

{{float_begin|side=right|width=200px}}
|-align=center
|<math>\{(a n + b)_{n=0}^\infty : a, b \in \mathbb{R}\}</math>
{{float_end|2-dimensional [[Sequence space|vector space of sequences]] generated by the sequence <math>s_n = n</math>.}}

A sequence <math>(s_n)_{n=0}^\infty</math> is constant-recursive if and only if the set of sequences
:<math>\left\{(s_{n+r})_{n=0}^\infty : r \geq 0\right\}</math>
is contained in a [[Sequence space|sequence space]] ([[Vector space|vector space]] of sequences) whose [[Dimension (vector space)|dimension]] is finite. That is, <math>(s_n)_{n=0}^\infty</math> is contained in a finite-dimensional [[Linear subspace|subspace]] of <math>\mathbb{C}^\mathbb{N}</math> [[Closure (mathematics)|closed]] under the [[Shift operator#Sequences|left-shift operator]].{{sfn|Kauers|Paule|2010|p=67}}

This characterization is because the order-<math>d</math> linear recurrence relation can be understood as a [[Linear independence#Definition|proof of linear dependence]] between the sequences <math>(s_{n+r})_{n=0}^\infty</math> for <math>r=0, \ldots, d</math>. An extension of this argument shows that the order of the sequence is equal to the dimension of the sequence space generated by <math>(s_{n+r})_{n=0}^\infty</math> for all <math>r</math>.{{sfn|Kauers|Paule|2010|p=69}}

== Closed-form characterization ==


{{float_begin|side=right|width=300px}}
|-align=center
|<math>F_n = \frac{1}{\sqrt{5}}(1.618\ldots)^n - \frac{1}{\sqrt{5}}(-0.618\ldots)^n</math>
{{float_end|Closed-form characterization of the Fibonacci sequence ([[Fibonacci number#Binet's formula|Binet's formula]])}}

Constant-recursive sequences admit the following unique [[Closed-form expression|closed form]] characterization using [[Exponential polynomial|exponential polynomial]]s: every constant-recursive sequence can be written in the form{{sfn|Brousseau|1971|pp=28-34|loc=Lesson 5}}
:<math>s_n = z_n + k_1(n) r_1^n + k_2(n) r_2^n + \cdots + k_e(n) r_e^n,</math>
where
* <math>z_n</math> is a sequence which is zero for all <math>n \ge d</math> (the order of the sequence);
* <math>k_1(n), k_2(n), \ldots, k_e(n)</math> are complex polynomials; and
* <math>r_1, r_2, \ldots, r_k</math> are distinct complex constants.

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 <math>F_n</math> is written in this form using [[Fibonacci number#Binet's formula|Binet's formula]]:{{sfn|Brousseau|1971|p=16|loc=Lesson 3}}
:<math>F_n = \frac{1}{\sqrt{5}}\varphi^n - \frac{1}{\sqrt{5}}\psi^n,</math>
where <math>\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\ldots</math> is the [[Golden ratio|golden ratio]] and <math>\psi = \frac{-1}{\varphi}</math>, both roots of the equation <math>x^2 - x - 1 = 0</math>. In this case, <math>e=2</math>, <math>z_n = 0</math> for all <math>n</math>, <math>k_1(n) = k_2(n) = \frac{1}{\sqrt{5}}</math> (constant polynomials), <math>r_1 = \varphi</math>, and <math>r_2 = \psi</math>. Notice that though the original sequence was over the integers, the closed form solution involves real or complex roots. In general, for sequences of integers or rationals, the closed formula will use [[Algebraic number|algebraic number]]s.

The complex numbers <math>r_1, \ldots, r_n</math> are the roots of the [[Characteristic equation (calculus)|characteristic polynomial]] (or "auxiliary polynomial") of the recurrence:
:<math>x^d - c_1 x^{d-1} - \dots - c_{d-1} x - c_d</math>
whose coefficients are the same as those of the recurrence.{{sfn|Brousseau|1971|p=28|loc=Lesson 5}}
If the <math>d</math> roots <math>r_1, r_2, \dots, r_d</math> are all distinct, then the polynomials <math>k_i(n)</math> 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 <math>r_i</math> is a root of [[Multiplicity (mathematics)|multiplicity]] <math>m</math>, then <math>k_i(n)</math> in the formula has degree <math>m - 1</math>. For instance, if the characteristic polynomial factors as <math>(x-r)^3</math>, with the same root ''r'' occurring three times, then the <math>n</math>th term is of the form <math>s_n = (a + b n + c n^2) r^n.</math><ref>{{citation|contribution=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| edition=2nd| publisher=Birkhäuser |page=17 | year=1982}}.</ref>{{sfn|Brousseau|1971|pp=29-31|loc=Lesson 5}}

The term <math>z_n</math> is only needed when <math>c_d\ne 0</math>; if <math>c_d = 0</math> then it corrects for the fact that some initial values may be exceptions to the general recurrence. In particular, <math>z_n = 0</math> for all <math>n \ge d</math>, the order of the sequence.

==Closure properties==

===Examples===

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 <math>s_n = 2^n</math> and <math>t_n = n</math> is <math>u_n = 2^n + n</math> (<math>1, 3, 6, 11, 20, \ldots</math>), which satisfies the recurrence <math>u_n = 4u_{n-1} - 5u_{n-2} + 2u_{n-3}</math>. 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 <math>s_n = 2^n</math> and <math>t_n = n</math> is <math>u_n = n \cdot 2^n</math> (<math>0, 2, 8, 24, 64, \ldots</math>), which satisfies the recurrence <math>u_n = 4 u_{n-1} - 4 u_{n-2}</math>.

The left-shift sequence <math>u_n = s_{n + 1}</math> and the right-shift sequence <math>u_n = s_{n - 1}</math> (with <math>u_0 = 0</math>) are constant-recursive because they satisfy the same recurrence relation. For example, because <math>s_n = 2^n</math> is constant-recursive, so is <math>u_n = 2^{n + 1}</math>.

===List of operations===

In general, constant-recursive sequences are [[Closure (mathematics)|closed]] under the following operations, where <math>s = (s_n)_{n \in \mathbb{N}}, t = (t_n)_{n \in \mathbb{N}}</math> denote constant-recursive sequences, <math>f(x), g(x)</math> are their generating functions, and <math>d, e</math> are their orders, respectively.

{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|+ Operations on constant-recursive sequences
! Operation !! Definition !! Requirement !! Generating function equivalent || Order
|-
| Term-wise sum <math>s + t</math> || <math>(s + t)_n = s_n + t_n</math> || — || <math>f(x) + g(x)</math> || <math>\le d + e</math>{{sfn|Kauers|Paule|2010|p=71}}
|-
| Term-wise product <math>s \cdot t</math> || <math>(s \cdot t)_n = s_n \cdot t_n</math> || — || — || <math> \le d \cdot e </math><ref name="ow"/>{{sfn|Kauers|Paule|2010|p=71}}
|-
| [[Cauchy product]] <math>s * t</math> || <math>(s * t)_n = \sum_{i=0}^n s_i t_{n-i}</math> || — || <math>f(x) g(x)</math> || <math>\le d + e</math>
|-
| Left shift <math>Ls</math> || <math>(Ls)_n = s_{n+1}</math> || — || <math>\frac{f(x) - s_0}{x}</math> || <math>\le d</math>
|-
| Right shift <math>Rs</math> || <math>(Rs)_n = \begin{cases}s_{n-1} &n \ge 1\\0 &n = 0\end{cases}</math> || — || <math>x f(x)</math> || <math>\le d + 1</math>
|-
| [[Formal power series#Multiplicative inverse|Cauchy inverse]] <math>s^{(-1)}</math> || <math>(s^{(-1)})_n = \sum_{{i_1 + \dots + i_k = n} \atop {i_1, \ldots, i_k \ne 0}} (-1)^k s_{i_1} s_{i_2} \cdots s_{i_k}</math> || <math>s_0 = 1</math> || <math>\frac{1}{f(x)}</math> || <math>\le \max(2d-1, 2)</math>
|-
| [[Kleene star]] <math>s^{(*)}</math> || <math>(s^{(*)})_n = \sum_{{i_1 + \dots + i_k = n} \atop {i_1, \ldots, i_k \ne 0}} s_{i_1} s_{i_2} \cdots s_{i_k}</math> || <math> s_0 = 0</math> || <math>\frac{1}{1 - f(x)}</math> || <math>\le \max(2d-1,2)</math>
|}

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 <math>s_0 = 1</math> for Cauchy inverse is necessary for the case of integer sequences, but can be replaced by <math>s_0 \ne 0</math> if the sequence is over any [[Field (mathematics)|field]] (rational, algebraic, real, or complex numbers).
<!--

TBD: closure operations characterization:
The constant-recursive sequences can be characterized as the smallest set of sequences containing the constants (in integer, rational, algebraic, or complex numbers) closed under pointwise addition, right-shift, Cauchy product, and either Cauchy inverse or Kleene star.
A characterization involving product might also be possible.
Need to include a citation for these statements.
-->

==Behavior==

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

===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 <math>n</math> such that <math>s_n = 0</math>. The Skolem–Mahler–Lech theorem states that the zeros of the sequence are eventually repeating: there exists constants <math>M</math> and <math>N</math> such that for all <math>n > M</math>, <math>s_n = 0</math> if and only if <math>s_{n+N} = 0</math>. This result holds for a constant-recursive sequence over the complex numbers, or more generally, over any [[Field (mathematics)|field]] of [[Characteristic (algebra)|characteristic]] zero.<ref>{{citation|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}}</ref>

===Decision problems===
The pattern of zeros in a constant-recursive sequence can also be investigated from the perspective of [[Computability theory|computability theory]]. To do so, the description of the sequence <math>s_n</math> must be given a [[String (computer science)|finite description]]; this can be done if the sequence is over the integers or rational numbers, or even over the algebraic numbers.<ref name="ow">{{citation
 | last1 = Ouaknine | first1 = Joël
 | last2 = Worrell | first2 = James
 | contribution = 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}}.</ref>
Given such an encoding for sequences <math>s_n</math>, the following problems can be studied:

{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|+ Notable decision problems
! Problem !! Description !! Status<ref name="ow"/><ref name=LICS22>{{Cite journal |last=Lipton |first=Richard |last2=Luca |first2=Florian |last3=Nieuwveld |first3=Joris |last4=Ouaknine |first4=Joël |last5=Purser |first5=David |last6=Worrell |first6=James |date=2022-08-04 |title=On the Skolem Problem and the Skolem Conjecture |url=https://dl.acm.org/doi/10.1145/3531130.3533328 |journal=Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science |series=LICS '22 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=1–9 |doi=10.1145/3531130.3533328 |isbn=978-1-4503-9351-5}}</ref>
|-
| Existence of a zero ([[Skolem problem]])
  || On input <math>(s_n)_{n=0}^\infty</math>, is <math>s_n = 0</math> for some <math>n</math>?
  || Open
|-
| Infinitely many zeros
  || On input <math>(s_n)_{n=0}^\infty</math>, is <math>s_n = 0</math> for infinitely many <math>n</math>?
  || Decidable
|-
| Eventually all zero
  || On input <math>(s_n)_{n=0}^\infty</math>, is <math>s_n = 0</math> for all [[Eventually (mathematics)|sufficiently large]] <math>n</math>?
  || Decidable
|-
| Positivity
  || On input <math>(s_n)_{n=0}^\infty</math>, is <math>s_n > 0</math> for all <math>n</math>?
  || Open
|-
| Eventual positivity
  || On input <math>(s_n)_{n=0}^\infty</math>, is <math>s_n > 0</math> for all [[Eventually (mathematics)|sufficiently large]] <math>n</math>?
  || Open
|}

Because the square of a constant-recursive sequence <math>s_n^2</math> is still constant-recursive (see closure properties), the existence-of-a-zero problem in the table above [[Reduction (recursion theory)|reduces to]] positivity, and infinitely-many-zeros reduces to eventual positivity. Other problems also reduce to those in the above table: for example, whether <math>s_n = c</math> for some <math>n</math> reduces to existence-of-a-zero for the sequence <math>s_n - c</math>. As a second example, for sequences in the real numbers, ''weak'' positivity (is <math>s_n \ge 0</math> for all <math>n</math>?) reduces to positivity of the sequence <math>-s_n</math> (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 [[Constructive proof|non-constructive]]. It states that for all <math>n > M</math>, the zeros are repeating; however, the value of <math>M</math> is not known to be computable, so this does not lead to a solution to the existence-of-a-zero problem.<ref name="ow"/> On the other hand, the exact pattern which repeats after <math>n > M</math> ''is'' computable.<ref name="ow"/><ref>{{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}}</ref> 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,<ref name="ow" /> and for a restricted set of sequences up to order 7.<ref name=LICS22/>

==Generalizations==

* A '''[[Holonomic function|holonomic sequence]]''' is a natural generalization where the coefficients of the recurrence are allowed to be polynomial functions of <math>n</math> rather than constants.
* A '''[[K-regular sequence|<math>k</math>-regular sequence]]''' satisfies a linear recurrences with constant coefficients, but the recurrences take a different form.  Rather than <math>s_n</math> being a linear combination of <math>s_m</math> for some integers <math>m</math> that are close to <math>n</math>, each term <math>s_n</math> in a <math>k</math>-regular sequence is a linear combination of <math>s_m</math> for some integers <math>m</math> whose [[Radix|base]]-<math>k</math> representations are close to that of <math>n</math>.  Constant-recursive sequences can be thought of as <math>1</math>-regular sequences, where the [[Unary numeral system|base-1 representation]] of <math>n</math> consists of <math>n</math> copies of the digit <math>1</math>.

==Notes==
{{reflist}}

==References==
{{refbegin}}
* {{Cite book|last1=Kauers|first1=Manuel|url=https://books.google.com/books?id=BPeODAEACAAJ|title=The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates|last2=Paule|first2=Peter|date=2010-12-01|publisher=Springer Vienna|isbn=978-3-7091-0444-6|language=en|pages=66}}
* {{cite book |first1=Alfred |last1=Brousseau |title=Linear Recursion and Fibonacci Sequences |year=1971 |publisher=Fibonacci Association |url=http://www.fq.math.ca/linear.html}}
{{refend}}

[[Category:Combinatorics]]
[[Category:Dynamical systems]]
[[Category:Integer sequences]]
[[Category:Linear algebra]]
[[Category:Recurrence relations]]

==External links==
* {{cite web |title= OEIS Index Rec|url=http://oeis.org/wiki/Index_to_OEIS:_Section_Rec}} [[On-Line Encyclopedia of Integer Sequences|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)

{{Sourceattribution|Constant-recursive sequence}}