→In terms of generating functions: change sum notation |
Caleb Stanford (talk | contribs) Switch to subscript notation throughout (s(n) -> s_n) Tag: 2017 wikitext editor |
||
Line 7: | Line 7: | ||
In [[mathematics]] and [[theoretical computer science]], a '''constant-recursive sequence''' (also known as a '''linear recurrence sequence''', '''linear-recursive sequence''', '''linear-recurrent sequence''', or '''C-finite sequence''') is an [[sequence|infinite sequence]] of [[number]]s in which each number in the sequence is equal to a [[linear combination]] of one or more of its immediate predecessors. |
In [[mathematics]] and [[theoretical computer science]], a '''constant-recursive sequence''' (also known as a '''linear recurrence sequence''', '''linear-recursive sequence''', '''linear-recurrent sequence''', or '''C-finite sequence''') is an [[sequence|infinite sequence]] of [[number]]s in which each number in the sequence is equal to a [[linear combination]] of one or more of its immediate predecessors. |
||
The most famous example of a constant-recursive sequence is the [[Fibonacci number|Fibonacci sequence]], in which each number is the sum of the previous two; formally, we say that it satisfies a [[linear recurrence with constant coefficients]] |
The most famous example of a constant-recursive sequence is the [[Fibonacci number|Fibonacci sequence]], in which each number is the sum of the previous two; formally, we say that it satisfies a [[linear recurrence with constant coefficients]] |
||
:<math display=block>F_n = F_{n-1} + F_{n-2},</math> |
|||
where <math>F_n</math> is the <math>n</math>th Fibonacci number. Generalizing this idea, a constant-recursive sequence <math>s_0, s_1, s_2, s_3, \ldots</math> satisfies a formula of the form |
|||
:<math display=block> |
:<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. In addition to the Fibonacci sequence, constant-recursive sequences include many other well-known sequences, such as [[arithmetic progression]]s, [[geometric progression]]s, and [[polynomial]]s. |
where <math>c_i</math> are [[Constant (mathematics)|constant]]s. In addition to the Fibonacci sequence, constant-recursive sequences include many other well-known sequences, such as [[arithmetic progression]]s, [[geometric progression]]s, and [[polynomial]]s. |
||
Line 15: | Line 17: | ||
==Definition== |
==Definition== |
||
An order-''d'' '''homogeneous [[linear recurrence with constant coefficients|linear recurrence relation]]''' is an equation of the form |
An order-''d'' '''homogeneous [[linear recurrence with constant coefficients|linear recurrence relation]]''' is an equation of the form |
||
:<math> |
:<math>s_n = c_1 s_{n-1} + c_2 s_{n-2} + \dots + c_d s_{n-d},</math> |
||
where the ''d'' coefficients <math>c_1, c_2, \dots, c_d</math> are coefficients ranging over the [[integer]]s, [[rational number]]s, [[algebraic number]]s, [[real number]]s, or [[complex number]]s. |
where the ''d'' coefficients <math>c_1, c_2, \dots, c_d</math> are coefficients ranging over the [[integer]]s, [[rational number]]s, [[algebraic number]]s, [[real number]]s, or [[complex number]]s. |
||
A [[sequence]] <math> |
A [[sequence]] <math>s_0, s_1, s_2, \dots</math> (written as <math>(s_n)_{n=0}^\infty</math> as a shorthand) ranging over the same domain as the coefficients, is '''constant-recursive''' if there is an order-''d'' homogeneous linear recurrence with constant coefficients that it satisfies for all <math>n \geq d</math>. This definition allows eventually-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>{{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}}</ref><ref name=Border>{{Citation|last1=Halava|first1=Vesa|title=Skolem's Problem – On the Border between Decidability and Undecidability|date=2005|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.155.2606|access-date=2021-11-28|last2=Harju|first2=Tero|last3=Hirvensalo|first3=Mika|last4=Karhumäki|first4=Juhani|citeseerx=10.1.1.155.2606|page=1}}</ref> |
||
The '''order''' of a constant-recursive sequence is the smallest <math>d \ge 1</math> such that the sequence satisfies an order-''d'' homogeneous linear recurrence, or <math>d = 0</math> for the everywhere-zero sequence. |
The '''order''' of a constant-recursive sequence is the smallest <math>d \ge 1</math> such that the sequence satisfies an order-''d'' homogeneous linear recurrence, or <math>d = 0</math> for the everywhere-zero sequence. |
||
Line 29: | Line 31: | ||
{{float_begin|side=right|width=225px}} |
{{float_begin|side=right|width=225px}} |
||
|-align=center |
|-align=center |
||
|<math> |
|<math>F_n = \begin{bmatrix}0 & 1\end{bmatrix} |
||
\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^n |
\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^n |
||
\begin{bmatrix}1 \\ 0\end{bmatrix}.</math> |
\begin{bmatrix}1 \\ 0\end{bmatrix}.</math> |
||
{{float_end|Definition of the Fibonacci sequence using matrices.}} |
{{float_end|Definition of the Fibonacci sequence using matrices.}} |
||
A sequence <math>( |
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> |
:<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, 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> |
where <math>u</math> is a <math>1 \times d</math> vector, <math>A</math> is a <math>d \times d</math> 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 vector spaces=== |
===In terms of vector spaces=== |
||
A sequence <math>( |
A sequence <math>(s_n)_{n=0}^\infty</math> is constant-recursive if and only if the set of sequences |
||
:<math>\left\{( |
:<math>\left\{(s_{n+r})_{n=0}^\infty : r \geq 0\right\}</math> |
||
is contained in a [[vector space]] whose [[Dimension (vector space)|dimension]] is finite, i.e. a finite-dimensional [[Linear subspace|subspace]] of <math>\mathbb{C}^\mathbb{N}</math> [[Closure (mathematics)|closed under]] the [[Shift operator#Sequences|left-shift operator]]. This is because the order-<math>d</math> linear recurrence relation can be understood as a [[Linear independence#Definition|proof of linear dependence]] between the vectors <math> |
is contained in a [[vector space]] whose [[Dimension (vector space)|dimension]] is finite, i.e. a finite-dimensional [[Linear subspace|subspace]] of <math>\mathbb{C}^\mathbb{N}</math> [[Closure (mathematics)|closed under]] the [[Shift operator#Sequences|left-shift operator]]. This is because the order-<math>d</math> linear recurrence relation can be understood as a [[Linear independence#Definition|proof of linear dependence]] between the vectors <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 vector space generated by <math>(s_{n+r})_{n=0}^\infty</math> for all <math>r</math>. |
||
===In terms of non-homogeneous linear recurrences=== |
===In terms of non-homogeneous linear recurrences=== |
||
Line 51: | Line 53: | ||
! Non-homogeneous !! Homogeneous |
! Non-homogeneous !! Homogeneous |
||
|- align = "center" |
|- align = "center" |
||
| <math> |
| <math>s_n = 1 + s_{n-1}</math> |
||
| <math> |
| <math>s_n = 2s_{n-1} - s_{n-2}</math> |
||
|- align = "center" |
|- align = "center" |
||
| <math> |
| <math>s_0 = 0</math> |
||
| <math> |
| <math>s_0 = 0; s_1 = 1</math> |
||
{{float_end|Definition of the sequence of [[natural number]]s <math> |
{{float_end|Definition of the sequence of [[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 |
A '''non-homogeneous''' linear recurrence is an equation of the form |
||
:<math> |
:<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> |
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} |
:<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 === |
=== In terms of generating functions === |
||
Line 67: | Line 69: | ||
{{float_begin|side=right|width=200px}} |
{{float_begin|side=right|width=200px}} |
||
|-align=center |
|-align=center |
||
|<math>\sum_{n = 0}^\infty |
|<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]].}} |
{{float_end|Definition of the Fibonacci sequence using a [[generating function]].}} |
||
A sequence is constant-recursive precisely when its [[generating function]] |
A sequence is constant-recursive precisely when its [[generating function]] |
||
:<math>\sum_{n = 0}^\infty |
:<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 [[polynomial]]s. 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.<ref>{{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}}</ref> The explicit derivation of the generating function in terms of the linear recurrence is |
is a [[rational function]] <math>\frac{p(x)}{q(x)}</math>, where <math>p</math> and <math>q</math> are [[polynomial]]s. 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.<ref>{{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}}</ref> The explicit derivation of the generating function in terms of the linear recurrence is |
||
:<math>\sum_{n = 0}^\infty |
:<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> |
</math> |
||
where |
where |
||
:<math>b_n = |
:<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). |
It follows from the above that the denominator here must be a polynomial not divisible by <math>x</math> (and in particular nonzero). |
||
Line 84: | Line 86: | ||
:<math>1 - c_1 x^1 - c_2 x^2 - \dots - c_d x^d</math> |
:<math>1 - c_1 x^1 - c_2 x^2 - \dots - c_d x^d</math> |
||
yields a series |
yields a series |
||
:<math>\left( |
:<math>\left(s_0 + s_1 x^1 + s_2 x^2 + \cdots\right) \left(1 - c_1 x^1 - c_2 x^2 - \dots - c_d x^d \right) = \left(b_0 + b_1 x^1 + b_2 x^2 + \cdots\right),</math> |
||
If <math> |
If <math>s_n</math> satisfies the recurrence relation |
||
:<math> |
:<math>s_n = c_1 s_{n-1} + c_2 s_{n-2} + \dots + c_d s_{n-d},</math> |
||
then <math>b_n = 0</math> for all <math>n \geq d</math>. In other words, |
then <math>b_n = 0</math> for all <math>n \geq d</math>. In other words, |
||
:<math>\left( |
:<math>\left(s_0 + s_1 x^1 + s_2 x^2 + \cdots\right) \left(1 - c_1 x^1 - c_2 x^2 - \dots - c_d x^d \right) = \left(b_0 + b_1 x^1 + b_2 x^2 + \dots + b_{d-1} x^{d-1}\right),</math> |
||
so we obtain the rational function |
so we obtain the rational function |
||
In the special case of a periodic sequence satisfying <math> |
In the special case of a periodic sequence satisfying <math>s_n = s_{n-d}</math> for <math>n \geq d</math>, the generating function is |
||
:<math>\begin{align}\frac{ |
:<math>\begin{align}\frac{s_0 + s_1 x^1 + \dots + s_{d-1} x^{d-1}}{1-x^d} =& \left(s_0 + s_1 x^1 + \dots + s_{d-1} x^{d-1}\right) + \left(s_0 + s_1 x^1 + \dots + s_{d-1} x^{d-1}\right) x^d + {}\\& \left(s_0 + s_1 x^1 + \dots + s_{d-1} x^{d-1}\right) x^{2d} + \cdots\end{align}</math> |
||
by expanding the geometric series. |
by expanding the geometric series. |
||
Line 104: | Line 106: | ||
! Name !! Order (<math>d</math>) !! First few values !! Recurrence (for <math>n \ge d</math>) !! Generating function !! OEIS |
! Name !! Order (<math>d</math>) !! First few values !! Recurrence (for <math>n \ge d</math>) !! Generating function !! OEIS |
||
|- |
|- |
||
| Zero sequence || 0 || 0, 0, 0, ... || <math> |
| Zero sequence || 0 || 0, 0, 0, ... || <math>s_n = 0</math> || <math>\frac{0}{1}</math> || {{OEIS link|A000004}} |
||
|- |
|- |
||
| One sequence || 1 || 1, 1, 1, ... || <math> |
| One sequence || 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, ... || <math> |
| [[Indicator function|Characteristic function]] of <math>\{0\}</math> || 1 || 1, 0, 0, 0, ... || <math>s_n = 0</math> || <math>\frac{1}{1}</math> || {{OEIS link|A000007}} |
||
|- |
|- |
||
| [[Power of two|Powers of two]] || 1 || 1, 2, 4, 8, 16, ... || <math> |
| [[Power of two|Powers of two]] || 1 || 1, 2, 4, 8, 16, ... || <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, ... || <math> |
| Powers of -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, ... || <math> |
| Characteristic function of <math>\{1\}</math> || 2 || 0, 1, 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, ... || <math> |
| [[Decimal representation|Decimal expansion]] of 1/6 || 2 || 1, 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, ... || <math> |
| Decimal expansion of 1/11 || 2 || 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, ... || <math> |
| [[Natural number|Nonnegative integers]] || 2 || 0, 1, 2, 3, 4, ... || <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, ... || <math> |
| [[Parity (mathematics)|Odd]] positive integers || 2 || 1, 3, 5, 7, 9, ... || <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> |
| [[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, ... || <math> |
| [[Lucas number]]s || 2 || 2, 1, 3, 4, 7, 11, ... || <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, ... || <math> |
| [[Pell number]]s || 2 || 0, 1, 2, 5, 12, 29, ... || <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> |
| 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]] || 2 || 1, 1, 0, -1, -1, 0, 1, 1, ... || <math> |
| Inverse of 6th [[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, ... || <math> |
| [[Triangular number]]s || 3 || 0, 1, 3, 6, 10, 15, ... || <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=== |
===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> |
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. |
||
===Arithmetic progressions=== |
===Arithmetic progressions=== |
||
For any <math>a</math> and any <math>r \ne 0</math>, the [[arithmetic progression]] <math>a, a+r, a+2r, \ldots</math> is constant-recursive of order 2, because it satisfies <math> |
For any <math>a</math> and any <math>r \ne 0</math>, the [[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=== |
===Geometric progressions=== |
||
For any <math>a \ne 0</math> and <math>r</math>, the [[geometric progression]] <math>a, a r, a r^2, \ldots</math> is constant-recursive of order 1, because it satisfies <math> |
For any <math>a \ne 0</math> and <math>r</math>, the [[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=== |
===Eventually periodic sequences=== |
||
A sequence that is eventually periodic with period length <math>\ell</math> is constant-recursive, since it satisfies <math> |
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=== |
===Polynomial sequences=== |
||
For any polynomial <math> |
For any polynomial <math>s_n</math>, the sequence of its values is a constant-recursive sequence. If the degree of the polynomial is <math>d</math>, the sequence satisfies a recurrence of order <math>d + 1</math>, with coefficients given by the corresponding element of the [[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> The first few such equations are |
||
:<math> |
:<math> s_n = 1 \cdot s_{n-1} </math> for a degree 0 (that is, constant) polynomial, |
||
:<math> |
:<math> s_n = 2\cdot s_{n-1} - 1\cdot s_{n-2} </math> for a degree 1 or less polynomial, |
||
:<math> |
:<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> |
:<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 proved in a number of ways, including via the theory of [[finite differences]].<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> |
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]].<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> |
||
Line 162: | Line 164: | ||
===Enumeration of words in a regular language=== |
===Enumeration of words in a regular language=== |
||
Let <math>L</math> be a [[regular language]], and let <math> |
Let <math>L</math> be a [[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. 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]] over the unary alphabet <math>\Sigma = \{a\}</math> over the semiring <math>(\mathbb{R}, +, \times)</math> is constant-recursive. |
||
===Other examples=== |
===Other examples=== |
||
Line 173: | Line 175: | ||
Constant-recursive sequences admit the following unique [[Closed-form expression|closed form]] characterization using [[exponential polynomial]]s: every constant-recursive sequence can be written in the form |
Constant-recursive sequences admit the following unique [[Closed-form expression|closed form]] characterization using [[exponential polynomial]]s: every constant-recursive sequence can be written in the form |
||
:<math> |
:<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 |
where |
||
* <math> |
* <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>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 number constants. |
* <math>r_1, r_2, \ldots, r_k</math> are distinct complex number constants. |
||
Line 181: | Line 183: | ||
This characterization is exact: every sequence of complex numbers that can be written in the above form is constant-recursive. |
This characterization is exact: every sequence of complex numbers that can be written in the above form is constant-recursive. |
||
For example, the Fibonacci number <math> |
For example, the Fibonacci number <math>F_n</math> is written in this form using [[Fibonacci number#Binet's formula|Binet's formula]]: |
||
:<math> |
:<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]] 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> |
where <math>\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\ldots</math> is the [[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]]s. |
||
The complex numbers <math>r_1, \ldots, r_n</math> are derived as the roots of the [[characteristic equation (calculus)|characteristic polynomial]] (or "auxiliary polynomial") of the recurrence: |
The complex numbers <math>r_1, \ldots, r_n</math> are derived as 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> |
:<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. |
whose coefficients are the same as those of the recurrence. |
||
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. The term <math> |
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. 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. |
||
In the general case where the roots of the characteristic polynomial are not necessarily distinct, and <math>r_i</math> is a root of [[Multiplicity (mathematics)|multiplicity]] <math>m</math>, the term <math>r_i^n</math> is multiplied by a degree-<math>(m-1)</math> polynomial in <math>n</math> (i.e. <math>k_i(n)</math> in the formula has degree <math>m</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 |
In the general case where the roots of the characteristic polynomial are not necessarily distinct, and <math>r_i</math> is a root of [[Multiplicity (mathematics)|multiplicity]] <math>m</math>, the term <math>r_i^n</math> is multiplied by a degree-<math>(m-1)</math> polynomial in <math>n</math> (i.e. <math>k_i(n)</math> in the formula has degree <math>m</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> |
:<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|author2-link=Donald Knuth| edition=2nd| publisher=Birkhäuser |page=17 | year=1982}}.</ref> |
||
==Closure properties== |
==Closure properties== |
||
Constant-recursive sequences are [[Closure (mathematics)|closed under]] the following operations, where <math> |
Constant-recursive sequences are [[Closure (mathematics)|closed under]] the following operations, where <math>(s_n), (t_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;" |
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;" |
||
Line 201: | Line 203: | ||
! Operation !! Definition !! Requirement !! Generating function equivalent || Order |
! Operation !! Definition !! Requirement !! Generating function equivalent || Order |
||
|- |
|- |
||
| Term-wise sum <math> |
| Term-wise sum <math>(s_n) + (t_n)</math> || <math>s_n + t_n</math> || — || <math>s(x) + t(x)</math> || <math>\le d + e</math> |
||
|- |
|- |
||
| Term-wise product <math> |
| Term-wise product <math>(s_n) \cdot (t_n)</math> || <math>s_n \cdot t_n</math> || — || — || <math> \le d \cdot e </math><ref name="ow"/> |
||
|- |
|- |
||
| [[Cauchy product]] <math> |
| [[Cauchy product]] <math>(s_n) * (t_n)</math> || <math>\sum_{i=0}^n s_i t_{n-i}</math> || — || <math>f(x) g(x)</math> || <math>\le d + e</math> |
||
|- |
|- |
||
| Left shift <math>L |
| Left shift <math>L (s_n)</math> || <math>s_{n+1}</math> || — || <math>\frac{f(x) - s_0}{x}</math> || <math>\le d</math> |
||
|- |
|- |
||
| Right shift <math>R |
| Right shift <math>R (s_n)</math> || <math>\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> |
| [[Formal power series#Multiplicative inverse|Cauchy inverse]] <math>(s_n)^{(-1)}</math> || — || <math>s_0 = 1</math> || <math>\frac{1}{f(x)}</math> || <math>\le \max(2d-1, 2)</math> |
||
|- |
|- |
||
| [[Kleene star]] <math> |
| [[Kleene star]] <math>(s_n)^{(*)}</math> || <math>\sum_{i_1 + \dots + i_k = n} 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> |
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). |
||
<!-- |
<!-- |
||
Line 230: | Line 232: | ||
===Zeros=== |
===Zeros=== |
||
Despite simple local dynamics, constant-recursive functions exhibit complex global behavior. Define a ''zero'' of a constant-recursive sequence to be a nonnegative integer <math>n</math> such that <math> |
Despite simple local dynamics, constant-recursive functions exhibit complex 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|doi-access=free}}</ref> |
||
===Decision problems=== |
===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 <math> |
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 <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 |
| last1 = Ouaknine | first1 = Joël |
||
| last2 = Worrell | first2 = James |
| last2 = Worrell | first2 = James |
||
Line 245: | Line 247: | ||
| volume = 7550 |
| volume = 7550 |
||
| year = 2012}}.</ref> |
| year = 2012}}.</ref> |
||
Given such an encoding for sequences <math> |
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;" |
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;" |
||
Line 252: | Line 254: | ||
|- |
|- |
||
| Existence of a zero ([[Skolem problem]]) |
| Existence of a zero ([[Skolem problem]]) |
||
|| On input <math> |
|| On input <math>(s_n)_{n=0}^\infty</math>, is <math>s_n = 0</math> for some <math>n</math>? |
||
|| Open |
|| Open |
||
|- |
|- |
||
| Infinitely many zeros |
| Infinitely many zeros |
||
|| On input <math> |
|| On input <math>(s_n)_{n=0}^\infty</math>, is <math>s_n = 0</math> for infinitely many <math>n</math>? |
||
|| Decidable |
|| Decidable |
||
|- |
|- |
||
| Positivity |
| Positivity |
||
|| On input <math> |
|| On input <math>(s_n)_{n=0}^\infty</math>, is <math>s_n > 0</math> for all <math>n</math>? |
||
|| Open |
|| Open |
||
|- |
|- |
||
| Eventual positivity |
| Eventual positivity |
||
|| On input <math> |
|| 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 |
|| Open |
||
|} |
|} |
||
Because the square of a constant-recursive sequence <math> |
Because the square of a constant-recursive sequence <math>s_n^2</math> is still constant-recursive (see [[#Closure properties|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|url=http://www.numdam.org/articles/10.24033/bsmf.1823/|journal=Bulletin de la Société Mathématique de France|language=fr|volume=104|pages=175–184|doi=10.24033/bsmf.1823}}</ref> This is why the infinitely-many-zeros problem is decidable: just determine if the infinitely-repeating pattern is empty. |
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|url=http://www.numdam.org/articles/10.24033/bsmf.1823/|journal=Bulletin de la Société Mathématique de France|language=fr|volume=104|pages=175–184|doi=10.24033/bsmf.1823}}</ref> This is why the infinitely-many-zeros problem is decidable: just determine if the infinitely-repeating pattern is empty. |
||
Line 278: | Line 280: | ||
* 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 '''[[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> |
* 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 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>. |
||
==Further reading== |
==Further reading== |
Revision as of 19:44, 26 January 2022
In mathematics and theoretical computer science, a constant-recursive sequence (also known as a linear recurrence sequence, linear-recursive sequence, linear-recurrent sequence, or C-finite sequence) is an infinite sequence of numbers in which each number in the sequence is equal to a linear combination of one or more of its immediate predecessors.
The most famous example of a constant-recursive sequence is the Fibonacci sequence, in which each number is the sum of the previous two; formally, we say that it satisfies a linear recurrence with constant coefficients
where is the th Fibonacci number. Generalizing this idea, a constant-recursive sequence satisfies a formula of the form
where are constants. In addition to the Fibonacci sequence, constant-recursive sequences include many other well-known sequences, such as arithmetic progressions, geometric progressions, and polynomials.
Constant-recursive sequences arise in combinatorics and the theory of finite differences; in algebraic number theory, due to the relation of the sequence to the roots of a polynomial; in the analysis of algorithms in the running time of simple recursive functions; and in formal language theory, 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. A seminal result is the Skolem–Mahler–Lech theorem, which states that the zeros of a constant-recursive sequence have a regularly repeating (eventually periodic) form. On the other hand, the Skolem problem, which asks for algorithm to determine whether a linear recurrence has at least one zero, remains one of the unsolved problems in mathematics.
Definition
An order-d homogeneous linear recurrence relation is an equation of the form
where the d coefficients are coefficients ranging over the integers, rational numbers, algebraic numbers, real numbers, or complex numbers.
A sequence (written as as a shorthand) ranging over the same domain as the coefficients, is constant-recursive if there is an order-d homogeneous linear recurrence with constant coefficients that it satisfies for all . This definition allows eventually-periodic sequences such as and . Some authors require that , which excludes such sequences.[1][2]
The order of a constant-recursive sequence is the smallest such that the sequence satisfies an order-d homogeneous linear recurrence, or for the everywhere-zero sequence.
Equivalent definitions
In terms of matrices
A sequence is constant-recursive of order if and only if it can be written as
where is a vector, is a matrix, and is a vector, where the elements come from the same domain (integers, rational numbers, algebraic numbers, real numbers, or complex numbers) as the original sequence. Specifically, can be taken to be the first values of the sequence, the linear transformation that computes from , and the vector .[3]
In terms of vector spaces
A sequence is constant-recursive if and only if the set of sequences
is contained in a vector space whose dimension is finite, i.e. a finite-dimensional subspace of closed under the left-shift operator. This is because the order- linear recurrence relation can be understood as a proof of linear dependence between the vectors for . An extension of this argument shows that the order of the sequence is equal to the dimension of the vector space generated by for all .
In terms of non-homogeneous linear recurrences
Non-homogeneous | Homogeneous |
---|---|
A non-homogeneous linear recurrence is an equation of the form
where is an additional constant. Any sequence satisfying a non-homogeneous linear recurrence is constant-recursive. This is because subtracting the equation for from the equation for yields a homogeneous recurrence for , from which we can solve for to obtain
In terms of generating functions
A sequence is constant-recursive precisely when its generating function
is a rational function , where and 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
where
It follows from the above that the denominator here must be a polynomial not divisible by (and in particular nonzero).
Examples
Name | Order () | First few values | Recurrence (for ) | Generating function | OEIS |
---|---|---|---|---|---|
Zero sequence | 0 | 0, 0, 0, ... | A000004 | ||
One sequence | 1 | 1, 1, 1, ... | A000012 | ||
Characteristic function of | 1 | 1, 0, 0, 0, ... | A000007 | ||
Powers of two | 1 | 1, 2, 4, 8, 16, ... | A000079 | ||
Powers of -1 | 1 | 1, -1, 1, -1, ... | A033999 | ||
Characteristic function of | 2 | 0, 1, 0, 0, 0, ... | A063524 | ||
Decimal expansion of 1/6 | 2 | 1, 6, 6, 6, ... | A020793 | ||
Decimal expansion of 1/11 | 2 | 0, 9, 0, 9, ... | A010680 | ||
Nonnegative integers | 2 | 0, 1, 2, 3, 4, ... | A001477 | ||
Odd positive integers | 2 | 1, 3, 5, 7, 9, ... | A005408 | ||
Fibonacci numbers | 2 | 0, 1, 1, 2, 3, 5, 8, 13, ... | A000045 | ||
Lucas numbers | 2 | 2, 1, 3, 4, 7, 11, ... | A000032 | ||
Pell numbers | 2 | 0, 1, 2, 5, 12, 29, ... | A000129 | ||
Powers of two interleaved with 0s | 2 | 1, 0, 2, 0, 4, 0, 8, 0, ... | A077957 | ||
Inverse of 6th cyclotomic polynomial | 2 | 1, 1, 0, -1, -1, 0, 1, 1, ... | A010892 | ||
Triangular numbers | 3 | 0, 1, 3, 6, 10, 15, ... | 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 with . For example, and . The sequence 2, 1, 3, 4, 7, 11, ... of Lucas numbers satisfies the same recurrence as the Fibonacci sequence but with initial conditions and . More generally, every Lucas sequence is constant-recursive of order 2.
Arithmetic progressions
For any and any , the arithmetic progression is constant-recursive of order 2, because it satisfies . Generalizing this, see polynomial sequences below.
Geometric progressions
For any and , the geometric progression is constant-recursive of order 1, because it satisfies . This includes, for example, the sequence 1, 2, 4, 8, 16, ... as well as the rational number sequence .
Eventually periodic sequences
A sequence that is eventually periodic with period length is constant-recursive, since it satisfies for all , where the order 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
For any polynomial , the sequence of its values is a constant-recursive sequence. If the degree of the polynomial is , the sequence satisfies a recurrence of order , with coefficients given by the corresponding element of the binomial transform.[5] The first few such equations are
- for a degree 0 (that is, constant) polynomial,
- for a degree 1 or less polynomial,
- for a degree 2 or less polynomial, and
- 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 integer, real, or complex values can be used as initial conditions for a constant-recursive sequence of order . If the initial conditions lie on a polynomial of degree or less, then the constant-recursive sequence also obeys a lower order equation.
Enumeration of words in a regular language
Let be a regular language, and let be the number of words of length in . Then is constant-recursive. For example, for the language of all binary strings, for the language of all unary strings, and 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 over the semiring is constant-recursive.
Other examples
The sequences of Jacobsthal numbers, Padovan numbers, Pell numbers, and Perrin numbers are constant-recursive.
Closed-form characterization
Constant-recursive sequences admit the following unique closed form characterization using exponential polynomials: every constant-recursive sequence can be written in the form
where
- is a sequence which is zero for all (the order of the sequence);
- are complex polynomials; and
- are distinct complex number constants.
This characterization is exact: every sequence of complex numbers that can be written in the above form is constant-recursive.
For example, the Fibonacci number is written in this form using Binet's formula:
where is the golden ratio and , both roots of the equation . In this case, , for all , (constant polynomials), , and . 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 numbers.
The complex numbers are derived as the roots of the characteristic polynomial (or "auxiliary polynomial") of the recurrence:
whose coefficients are the same as those of the recurrence. If the roots are all distinct, then the polynomials are all constants, which can be determined from the initial values of the sequence. The term is only needed when ; if then it corrects for the fact that some initial values may be exceptions to the general recurrence. In particular, for all , the order of the sequence.
In the general case where the roots of the characteristic polynomial are not necessarily distinct, and is a root of multiplicity , the term is multiplied by a degree- polynomial in (i.e. in the formula has degree ). For instance, if the characteristic polynomial factors as , with the same root r occurring three times, then the th term is of the form
Closure properties
Constant-recursive sequences are closed under the following operations, where denote constant-recursive sequences, are their generating functions, and are their orders, respectively.
Operation | Definition | Requirement | Generating function equivalent | Order |
---|---|---|---|---|
Term-wise sum | — | |||
Term-wise product | — | — | [3] | |
Cauchy product | — | |||
Left shift | — | |||
Right shift | — | |||
Cauchy inverse | — | |||
Kleene star |
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 for Cauchy inverse is necessary for the case of integer sequences, but can be replaced by if the sequence is over any field (rational, algebraic, real, or complex numbers).
Behavior
Zeros
Despite simple local dynamics, constant-recursive functions exhibit complex global behavior. Define a zero of a constant-recursive sequence to be a nonnegative integer such that . The Skolem–Mahler–Lech theorem states that the zeros of the sequence are eventually repeating: there exists constants and such that for all , if and only if . This result holds for a constant-recursive sequence over the complex numbers, or more generally, over any field of characteristic zero.[8]
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 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 , the following problems can be studied:
Problem | Description | Status (2021) |
---|---|---|
Existence of a zero (Skolem problem) | On input , is for some ? | Open |
Infinitely many zeros | On input , is for infinitely many ? | Decidable |
Positivity | On input , is for all ? | Open |
Eventual positivity | On input , is for all sufficiently large ? | Open |
Because the square of a constant-recursive sequence 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 for some reduces to existence-of-a-zero for the sequence . As a second example, for sequences in the real numbers, weak positivity (is for all ?) reduces to positivity of the sequence (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 , the zeros are repeating; however, the value of 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 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]
Generalizations
- A holonomic sequence is a natural generalization where the coefficients of the recurrence are allowed to be polynomial functions of rather than constants.
- A -regular sequence satisfies a linear recurrences with constant coefficients, but the recurrences take a different form. Rather than being a linear combination of for some integers that are close to , each term in a -regular sequence is a linear combination of for some integers whose base- representations are close to that of . Constant-recursive sequences can be thought of as -regular sequences, where the base-1 representation of consists of copies of the digit .
Further reading
- "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)
- Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association.
- Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics: A Foundation for Computer Science (2 ed.). Addison-Wesley. ISBN 978-0-201-55802-9.
References
- ^ Kauers, Manuel; Paule, Peter (2010-12-01). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6.
- ^ 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, retrieved 2021-11-28
- ^ a b c d e f 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, MR 3040104.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Lech, C. (1953), "A Note on Recurring Series", Arkiv för Matematik, 2 (5): 417–421, doi:10.1007/bf02590997
- ^ 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.