THC Science

The Fibonacci sequence is constant-recursive: each element of the sequence is the sum of the previous two.

Hasse diagram of some subsets of constant-recursive sequences, ordered by inclusion

In mathematics and theoretical computer science, a constant-recursive sequence or linear recurrence 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 the linear recurrence relation $F(n)=F(n-1)+F(n-2)$ , where $F(n)$ is the $n$ th Fibonacci number. Generalizing this idea, a constant-recursive sequence $s(n)$ satisfies a formula of the form

s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\dots +c_{d}s(n-d),

where $c_{i}$ 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

s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\dots +c_{d}s(n-d),

where the d coefficients $c_{1},c_{2},\dots ,c_{d}$ are coefficients ranging over the integers, rational numbers, algebraic numbers, real numbers, or complex numbers.

A sequence $s(0),s(1),s(2),\dots$ (ranging over the same domain as the coefficients) is a constant-recursive sequence if there is an order-d homogeneous linear recurrence with constant coefficients that it satisfies for all $n\geq d$ . Note that this definition allows eventually-periodic sequences such as $1,0,0,0,\ldots$ and $0,1,0,0,\ldots$ , which are disallowed by some authors.^[1] These sequences can be excluded by requiring that $c_{d}\neq 0$ .

The order of a constant-recursive sequence is the smallest $d\geq 1$ such that the sequence satisfies an order-d homogeneous linear recurrence, or $d=0$ for the everywhere-zero sequence.

Equivalent definitions

In terms of matrices

F(n)={\begin{bmatrix}0&1\end{bmatrix}}{\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}{\begin{bmatrix}1\\0\end{bmatrix}}.

Definition of the Fibonacci sequence using matrices.

A sequence $s(n)_{n\geq 0}$ is constant-recursive of order $\leq d$ if and only if it can be written as

s(n)=uA^{n}v

where $u$ is a $1\times d$ vector, $A$ is a $d\times d$ matrix, and $v$ is a $d\times 1$ vector, where the elements come from the same domain (integers, rational numbers, algebraic numbers, real numbers, or complex numbers) as the original sequence. Specifically, $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),\ldots ,s(n+d)$ from $s(n),s(n+1),\ldots ,s(n+d-1)$ , and $u$ the vector $0,0,\ldots ,0,1$ .

In terms of vector spaces

A sequence $s(n)_{n\geq 0}$ is constant-recursive if and only if the set of sequences

\{s(n+r)_{n\geq 0}:r\geq 0\}

is contained in a vector space whose dimension is finite, i.e. a finite-dimensional subspace of $\mathbb {C} ^{\mathbb {N} }$ closed under the left-shift operator. This is because the order- $d$ linear recurrence relation can be understood as a proof of linear dependence between the vectors $s(n+r)_{n\geq 0}$ for $r=0,\ldots ,d$ . An extension of this argument shows that the order of the sequence is equal to the dimension of the vector space generated by $s(n+r)_{n\geq 0}$ for all $r$ .

In terms of non-homogeneous linear recurrences

Non-homogeneous	Homogeneous
$s(n)=1+s(n-1)$	$s(n)=2s(n-1)-s(n-2)$
$s(0)=0$	$s(0)=0;s(1)=1$

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)+\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

{\begin{aligned}s(n)=&(c_{1}+1)s(n-1)\\&+(c_{2}-c_{1})s(n-2)+\dots +(c_{d}-c_{d-1})s(n-d)\\&-c_{d}s(n-d-1).\end{aligned}}

In terms of generating functions

\sum _{n\geq 0}F(n)x^{n}={\frac {x}{1-x-x^{2}}}.

Definition of the Fibonacci sequence using a generating function.

A sequence is constant-recursive precisely when its generating function

\sum _{n\geq 0}s(n)x^{n}=s(0)+s(1)x^{1}+s(2)x^{2}+s(3)x^{3}+\cdots

is a rational function ${\frac {p(x)}{q(x)}}$ , where $p$ and $q$ are polynomials. The denominator is the polynomial obtained from the auxiliary polynomial by reversing the order of the coefficients, and the numerator is determined by the initial values of the sequence.^[2] Note that the denominator here must be a polynomial not divisible by $x$ (and in particular nonzero). The explicit derivation of the generating function in terms of the linear recurrence is

\sum _{n\geq 0}s(n)x^{n}={\frac {b_{0}+b_{1}x^{1}+b_{2}x^{2}+\dots +b_{d-1}x^{d-1}}{1-c_{1}x^{1}-c_{2}x^{2}-\dots -c_{d}x^{d}}},

where

b_{n}=s(n)-c_{1}s(n-1)-c_{2}s(n-2)-\dots -c_{d}s(n-d).

Examples

Selected examples of integer constant-recursive sequences
Name	Order ( $d$ )	First few values	Recurrence (for $n\geq d$ )	Generating function	OEIS
Zero sequence	0	0, 0, 0, ...	$s(n)=0$	${\frac {0}{1}}$	A000004
One sequence	1	1, 1, 1, ...	$s(n)=s(n-1)$	${\frac {1}{1-x}}$	A000012
Characteristic function of $\{0\}$	1	1, 0, 0, 0, ...	$s(n)=0$	${\frac {1}{1}}$	A000007
Powers of two	1	1, 2, 4, 8, 16, ...	$s(n)=2s(n-1)$	${\frac {1}{1-2x}}$	A000079
Powers of -1	1	1, -1, 1, -1, ...	$s(n)=-s(n-1)$	${\frac {1}{1+x}}$	A033999
Characteristic function of $\{1\}$	2	0, 1, 0, 0, 0, ...	$s(n)=0$	${\frac {x}{1}}$	A063524
Decimal expansion of 1/6	2	1, 6, 6, 6, ...	$s(n)=s(n-1)$	${\frac {1+5x}{1-x}}$	A020793
Decimal expansion of 1/11	2	0, 9, 0, 9, ...	$s(n)=s(n-2)$	${\frac {9x}{1-x^{2}}}$	A010680
Nonnegative integers	2	0, 1, 2, 3, 4, ...	$s(n)=2s(n-1)-s(n-2)$	${\frac {x}{(1-x)^{2}}}$	A001477
Odd positive integers	2	1, 3, 5, 7, 9, ...	$s(n)=2s(n-1)-s(n-2)$	${\frac {1+x}{(1-x)^{2}}}$	A005408
Fibonacci numbers	2	0, 1, 1, 2, 3, 5, 8, 13, ...	$s(n)=s(n-1)+s(n-2)$	${\frac {x}{1-x-x^{2}}}$	A000045
Lucas numbers	2	2, 1, 3, 4, 7, 11, ...	$s(n)=s(n-1)+s(n-2)$	${\frac {2-x}{1-x-x^{2}}}$	A000032
Pell numbers	2	0, 1, 2, 5, 12, 29, ...	$s(n)=2s(n-1)+s(n-2)$	${\frac {x}{1-2x-x^{2}}}$	A000129
Inverse of 6th cyclotomic polynomial	2	1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, ...	$s(n)=s(n-1)-s(n-2)$	${\frac {1}{1-x+x^{2}}}$	A010892
Triangle numbers	3	0, 1, 3, 6, 10, 15, ...	$s(n)=3s(n-1)-3s(n-2)+s(n-3)$	${\frac {x}{(1-x)^{3}}}$	A000217

Fibonacci sequence

The sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 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$ .

Lucas sequences

The sequence 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ... (sequence A000032 in the OEIS) 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.

Arithmetic progressions

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

Geometric progressions

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

Eventually periodic sequences

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

Polynomial sequences

For any polynomial $s(n)$ , the sequence of its values is a constant-recursive sequence. If the degree of the polynomial is $d$ , the sequence satisfies a recurrence of order $d+1$ , with coefficients given by the corresponding element of the binomial transform.^[3] The first few such equations are

s(n)=1\cdot s(n-1)

for a degree 0 (that is, constant) polynomial,

s(n)=2\cdot s(n-1)-1\cdot s(n-2)

for a degree 1 or less polynomial,

s(n)=3\cdot s(n-1)-3\cdot s(n-2)+1\cdot s(n-3)

for a degree 2 or less polynomial, and

s(n)=4\cdot s(n-1)-6\cdot s(n-2)+4\cdot s(n-3)-1\cdot s(n-4)

for a degree 3 or less polynomial.

A sequence obeying the order-d equation also obeys all higher order equations. These identities may be proved in a number of ways, including via the theory of finite differences.^[4] 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.

Enumeration of words in a regular language

Let $L$ be a regular language, and let $s(n)$ be the number of words of length $n$ in $L$ . Then $s(n)_{n\geq 0}$ is constant-recursive. 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 $\Sigma =\{a\}$ over the semiring $(\mathbb {R} ,+,\times )$ 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

s(n)=z(n)+k_{1}(n)r_{1}^{n}+k_{2}(n)r_{2}^{n}+\cdots +k_{e}(n)r_{e}^{n},

where

$z(n)$ is a sequence which is zero for all but finitely many $n$ ;
$k_{1}(n),k_{2}(n),\ldots ,k_{e}(n)$ are complex polynomials; and
$r_{1},r_{2},\ldots ,r_{k}$ 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 $F(n)$ is written in this form using Binet's formula:

F(n)={\frac {1}{\sqrt {5}}}\varphi ^{n}+{\frac {1}{\sqrt {5}}}\psi ^{n},

where $\varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.61803\ldots$ is the Golden ratio and $\psi ={\frac {-1}{\varphi }}$ , both 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)={\frac {1}{\sqrt {5}}}$ (constant polynomials), $r_{1}=\varphi$ , and $r_{2}=\psi$ . 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 $r_{1},\ldots ,r_{n}$ are derived as the roots of the characteristic polynomial (or "auxiliary polynomial") of the recurrence:

x^{d}-c_{1}x^{d-1}-\dots -c_{d-1}x-c_{d}

whose coefficients are the same as those of the recurrence. If the $d$ roots $r_{1},r_{2},\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. The term $z(n)$ is only needed when $c(d)\neq 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\geq d$ , the order of the sequence.

In the general case where the roots of the characteristic polynomial are not necessarily distinct, and $r_{i}$ is a root of multiplicity $m$ , the term $r_{i}^{n}$ is multiplied by a degree- $(m-1)$ polynomial in $n$ (i.e. $k_{i}(n)$ in the formula has degree $m$ ). 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+bn+cn^{2})r^{n}.

^[5]

Derivation of the closed form

The closed form can be derived from the generating function via partial fraction decomposition. Specifically, if the generating function is written as

{\frac {f(x)}{g(x)}}=p(x)+\sum _{i}{\frac {f_{i}(x)}{(x-r_{i})^{m_{i}}}}

then the polynomial $p(x)$ determines the initial set of corrections $z(n)$ , the denominator $(x-r_{i})^{m}$ determines the exponential term $r_{i}^{n}$ , and the degree $m$ together with the numerator $f_{i}(x)$ determine the polynomial coefficient $k_{i}(n)$ .

Closure properties

Constant-recursive sequences are closed under the following operations, where $s(n),s_{1}(n),s_{2}(n)$ denote constant-recursive sequences, $f(x),f_{1}(x),f_{2}(x)$ are their generating functions, and $d,d_{1},d_{2}$ are their orders, respectively.

Operations on constant-recursive sequences
Operation	Definition	Requirement	Generating Function Equivalent	Order
Term-wise sum $s_{1}+s_{2}$	$s_{1}(n)+s_{2}(n)$	—	$f_{1}(x)+f_{2}(x)$	$\leq d_{1}+d_{2}$
Term-wise product $s_{1}\cdot s_{2}$	$s_{1}(n)\cdot s_{2}(n)$	—	—	$\leq d_{1}d_{2}$ ^[6]
Cauchy product $s_{1}*s_{2}$	$\sum _{i=0}^{n}s_{1}(i)s_{2}(n-i)$	—	$f_{1}(x)f_{2}(x)$	$\leq d_{1}+d_{2}$
Left shift $Ls$	$s(n+1)$	—	${\frac {f(x)-s(0)}{x}}$	$\leq d$
Right shift $Rs$	${\begin{cases}s(n-1)&n\geq 1\\0&n=0\end{cases}}$	—	$xf(x)$	$\leq d+1$
Cauchy inverse $s^{(-1)}$	—	$s(0)=1$	${\frac {1}{f(x)}}$	—
Kleene star $s^{(*)}$	$\sum _{i_{1}+\ldots +i_{k}=n}s(i_{1})s(i_{2})\cdots s(i_{k})$	$s(0)=0$	${\frac {1}{1-f(x)}}$	—

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 $s(0)=1$ for Cauchy inverse is necessary for the case of integer sequences, but can be replaced by $s(0)\neq 0$ 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 $n$ such that $s(n)=0$ . It is known via the Skolem–Mahler–Lech theorem 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.^[7]

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 $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.^[6] Given such an encoding for sequences $s(n)$ , the following problems can be studied:

Notable decision problems
Problem	Description	Status (2021)
Existence of a zero (Skolem problem)	On input $s(n)$ , is $s(n)=0$ for some $n$ ?	Open
Infinitely many zeros	On input $s(n)$ , is $s(n)=0$ for infinitely many $n$ ?	Decidable
Positivity	On input $s(n)$ , is $s(n)>0$ for all $n$ ?	Open
Eventual positivity	On input $s(n)$ , is $s(n)>0$ for all sufficiently large $n$ ?	Open

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. Many 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)\geq 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 discussed above would answer all of the above 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.^[6] On the other hand, the exact pattern which repeats after $n>M$ is computable.^[6] This is why the infinitely-many-zeros problem is decidable: just determine if the infinitely-repeating pattern is empty.

Generalizations

A holonomic sequence is a natural generalization where the coefficients of the recurrence are allowed to be polynomial functions of $n$ rather than constants.

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$ . 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$ .

General references

"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.

Notes

^ Kauers, Manuel; Paule, Peter (2010-12-01). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. ISBN 978-3-7091-0444-6.
^ 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.
^ Boyadzhiev, Boyad (2012). "Close Encounters with the Stirling Numbers of the Second Kind" (PDF). Math. Mag. 85: 252–266.
^ 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.
^ ^a ^b ^c ^d 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.
^ Lech, C. (1953), "A Note on Recurring Series", Arkiv för Matematik, 2: 417–421, doi:10.1007/bf02590997

[1] Kauers, Manuel; Paule, Peter (2010-12-01). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Springer Vienna. ISBN 978-3-7091-0444-6.

[2] 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.

[3] Boyadzhiev, Boyad (2012). "Close Encounters with the Stirling Numbers of the Second Kind" (PDF). Math. Mag. 85: 252–266.

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

[5] 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.

[ow-6] 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.

[7] Lech, C. (1953), "A Note on Recurring Series", Arkiv för Matematik, 2: 417–421, doi:10.1007/bf02590997

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 97: / Line 97: @@
 ==Examples==
+{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
+|+ Selected examples of integer constant-recursive sequences
+! 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>s(n) = 0</math> || <math>\frac{0}{1}</math> || {{OEIS link|A000004}}
+|-
+| One sequence || 1 || 1, 1, 1, ... || <math>s(n) = s(n-1)</math> || <math>\frac{1}{1-x}</math> || {{OEIS link|A000012}}
+|-
+| Characteristic function of <math>\{0\}</math> || 1 || 1, 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, ... || <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>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>s(n) = 0</math> || <math>\frac{x}{1}</math> || {{OEIS link|A063524}}
+|-
+| 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>s(n) = s(n-2)</math> || <math>\frac{9x}{1-x^2}</math> || {{OEIS link|A010680}}
+|-
+| 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}}
+|-
+| 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 numbers || 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 numbers || 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 numbers || 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}}
+|-
+| Inverse of 6th cyclotomic polynomial || 2 || 1, 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, 0, ... || <math>s(n) = s(n-1) - s(n-2)</math> || <math>\frac{1}{1-x+x^2}</math> || {{OEIS link|A010892}}
+|-
+| Triangle numbers || 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 sequence===