In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
, a constant-recursive sequence is an
infinite sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called t ...
of
number
A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual numbers c ...
s where each number in the sequence is equal to a fixed
linear combination of one or more of its immediate predecessors. A constant-recursive sequence is also known as a linear recurrence sequence, linear-recursive sequence, linear-recurrent sequence, a C-finite sequence, or a solution to a
linear recurrence with constant coefficients
In mathematics (including combinatorics, linear algebra, and dynamical systems), a linear recurrence with constant coefficients (also known as a linear recurrence relation or linear difference equation) sets equal to 0 a polynomial that is linear ...
.
The most famous example of a constant-recursive sequence is the
Fibonacci sequence
In mathematics, the Fibonacci numbers, commonly denoted , form a integer sequence, sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start ...
, in which each number is the sum of the previous two. The
power of two sequence is also constant-recursive because each number is the sum of twice the previous number. The
square number
In mathematics, a square number or perfect square is an integer that is the square (algebra), square of an integer; in other words, it is the multiplication, product of some integer with itself. For example, 9 is a square number, since it equals ...
sequence
is also constant-recursive. However, not all sequences are constant-recursive; for example, the
factorial number sequence is not constant-recursive. All
arithmetic progression
An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
s, all
geometric progression
In mathematics, a geometric progression, also known as a geometric sequence, is a sequence of non-zero numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the ''common ratio''. For e ...
s, and all
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
s are constant-recursive.
Formally, a sequence of numbers
is constant-recursive if it satisfies a
recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
:
where
are constants. For example, the Fibonacci sequence satisfies the recurrence relation
where
is the
th Fibonacci number.
Constant-recursive sequences are studied in
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
and the theory of
finite difference
A finite difference is a mathematical expression of the form . If a finite difference is divided by , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for t ...
s. They also arise in
algebraic number theory
Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations. Number-theoretic questions are expressed in terms of properties of algebraic ob ...
, due to the relation of the sequence to the roots of a polynomial; in the
analysis of algorithms
In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that re ...
as the running time of simple
recursive functions; and in
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
, where they count strings up to a given length in a
regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
. Constant-recursive sequences are
closed under
In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, but n ...
important mathematical operations such as
term-wise addition
Addition (usually signified by the Plus and minus signs#Plus sign, plus symbol ) is one of the four basic Operation (mathematics), operations of arithmetic, the other three being subtraction, multiplication and Division (mathematics), division. ...
, term-wise
multiplication
Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...
, and
Cauchy product In mathematics, more specifically in mathematical analysis, the Cauchy product is the discrete convolution of two infinite series. It is named after the French mathematician Augustin-Louis Cauchy.
Definitions
The Cauchy product may apply to infinit ...
.
The
Skolem–Mahler–Lech theorem
In additive and algebraic number theory, the Skolem–Mahler–Lech theorem states that if a sequence of numbers satisfies a linear difference equation, then with finitely many exceptions the positions at which the sequence is zero form a regularl ...
states that the
zeros of a constant-recursive sequence have a regularly repeating (eventually periodic) form. On the other hand, the
Skolem problem
In mathematics, the Skolem problem is the problem of determining whether the values of a constant-recursive sequence include the number zero. The problem can be formulated for recurrences over different types of numbers, including integers, ratio ...
, which asks for
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
to determine whether a linear recurrence has at least one zero, is a famous
unsolved problem in mathematics.
Definition
A constant-recursive sequence is any sequence of
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s,
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s,
algebraic number
An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the po ...
s,
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s, or
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
s
(written as
as a shorthand) satisfying a formula of the form
:
for all
where
are
constants.
(This equation is called a
linear recurrence with constant coefficients
In mathematics (including combinatorics, linear algebra, and dynamical systems), a linear recurrence with constant coefficients (also known as a linear recurrence relation or linear difference equation) sets equal to 0 a polynomial that is linear ...
of order ''d''.)
The order of the constant-recursive sequence is the smallest
such that the sequence satisfies a formula of the above form, or
for the everywhere-zero sequence.
The ''d'' coefficients
must be coefficients ranging over the same domain as the sequence (
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
s,
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s,
algebraic number
An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the po ...
s,
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
s, or
complex number
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted , called the imaginary unit and satisfying the equation i^= -1; every complex number can be expressed in the form ...
s). For example for a rational constant-recursive sequence,
and
must be rational numbers.
The definition above allows eventually-periodic sequences such as
and
. Some authors require that
, which excludes such sequences.
Examples
Fibonacci and Lucas sequences
The sequence 0, 1, 1, 2, 3, 5, 8, 13, ... of
Fibonacci number
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
s 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 number
The Lucas numbers or Lucas series are an integer sequence named after the mathematician François Édouard Anatole Lucas (1842–1891), who studied both that sequence and the closely related Fibonacci numbers. Lucas numbers and Fibonacci nu ...
s satisfies the same recurrence as the Fibonacci sequence but with initial conditions
and
. More generally, every
Lucas sequence
In mathematics, the Lucas sequences U_n(P,Q) and V_n(P, Q) are certain constant-recursive integer sequences that satisfy the recurrence relation
: x_n = P \cdot x_ - Q \cdot x_
where P and Q are fixed integers. Any sequence satisfying this recu ...
is constant-recursive of order 2.
Arithmetic progressions
For any
and any
, the
arithmetic progression
An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...
is constant-recursive of order 2, because it satisfies
. Generalizing this, see
polynomial sequences below.
Geometric progressions
For any
and
, the
geometric progression
In mathematics, a geometric progression, also known as a geometric sequence, is a sequence of non-zero numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the ''common ratio''. For e ...
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
A sequence defined by a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
is constant-recursive. The sequence satisfies a recurrence of order
(where
is the degree of the polynomial), with coefficients given by the corresponding element of the
binomial transform In combinatorics, the binomial transform is a sequence transformation (i.e., a transform of a sequence) that computes its forward differences. It is closely related to the Euler transform, which is the result of applying the binomial transform to th ...
. 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
A finite difference is a mathematical expression of the form . If a finite difference is divided by , one gets a difference quotient. The approximation of derivatives by finite differences plays a central role in finite difference methods for the ...
.
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
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
, 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
In theoretical computer science and formal language theory, a weighted automaton or weighted finite-state machine is a generalization of a finite-state machine in which the edges have weights, for example real numbers or integers. Finite-state ...
over the unary alphabet
over the semiring
is constant-recursive.
Other examples
The sequences of
Jacobsthal number In mathematics, the Jacobsthal numbers are an integer sequence named after the German mathematician Ernst Jacobsthal. Like the related Fibonacci numbers, they are a specific type of Lucas sequence U_n(P,Q) for which ''P'' = 1, and ''Q''& ...
s,
Padovan number
In number theory, the Padovan sequence is the sequence of integers ''P''(''n'') defined. by the initial values
:P(0)=P(1)=P(2)=1,
and the recurrence relation
:P(n)=P(n-2)+P(n-3).
The first few values of ''P''(''n'') are
:1, 1, 1, 2, 2, 3, 4, 5 ...
s,
Pell number
In mathematics, the Pell numbers are an infinite sequence of integers, known since ancient times, that comprise the denominators of the closest rational approximations to the square root of 2. This sequence of approximations begins , , , , an ...
s, and
Perrin number
In mathematics, the Perrin numbers are defined by the recurrence relation
: for ,
with initial values
:.
The sequence of Perrin numbers starts with
: 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, ...
The number of different maxima ...
s are constant-recursive.
Non-examples
The
factorial
In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times (n-1) \times (n-2) \t ...
number sequence
is not constant-recursive. More generally, every constant-recursive function is asymptotically bounded by an
exponential function
The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, a ...
(see
#Closed-form characterization) and the factorial sequence grows faster than this.
The
Catalan
Catalan may refer to:
Catalonia
From, or related to Catalonia:
* Catalan language, a Romance language
* Catalans, an ethnic group formed by the people from, or with origins in, Northern or southern Catalonia
Places
* 13178 Catalan, asteroid #1 ...
number sequence
is not constant-recursive. This is because the
generating function of the Catalan numbers is not a rational function (see
#Equivalent definitions).
Equivalent definitions
In terms of matrices
, -align=center
,
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
.
In terms of non-homogeneous linear recurrences
, - class="wikitable"
! Non-homogeneous !! Homogeneous
, - align = "center"
,
,
, - align = "center"
,
,
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
, -align=center
,
A sequence is constant-recursive precisely when its
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
:
is a
rational function
In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be rat ...
, where
and
are
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
s and
. 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.
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).
In terms of sequence spaces
, -align=center
,
A sequence
is constant-recursive if and only if the set of sequences
:
is contained in a
sequence space
In functional analysis and related areas of mathematics, a sequence space is a vector space whose elements are infinite sequences of real or complex numbers. Equivalently, it is a function space whose elements are functions from the natural num ...
(
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
of sequences) whose
dimension
In physics and mathematics, the dimension of a Space (mathematics), mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any Point (geometry), point within it. Thus, a Line (geometry), lin ...
is finite. That is,
is contained in a finite-dimensional
subspace of
closed under
In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, but n ...
the
left-shift operator.
This characterization is because the order-
linear recurrence relation can be understood as a
proof of linear dependence between the sequences
for
. An extension of this argument shows that the order of the sequence is equal to the dimension of the sequence space generated by
for all
.
Closed-form characterization
, -align=center
,
Constant-recursive sequences admit the following unique
closed form characterization using
exponential polynomial
In mathematics, exponential polynomials are functions on fields, rings, or abelian groups that take the form of polynomials in a variable and an exponential function.
Definition In fields
An exponential polynomial generally has both a variable ' ...
s: 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
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
:
:
where
is the
golden ratio
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities a and b with a > b > 0,
where the Greek letter phi ( ...
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 number
An algebraic number is a number that is a root of a non-zero polynomial in one variable with integer (or, equivalently, rational) coefficients. For example, the golden ratio, (1 + \sqrt)/2, is an algebraic number, because it is a root of the po ...
s.
The complex numbers
are the roots of the
characteristic polynomial
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The chara ...
(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.
If the roots of the characteristic polynomial are not distinct, and
is a root of
multiplicity
Multiplicity may refer to: In science and the humanities
* Multiplicity (mathematics), the number of times an element is repeated in a multiset
* Multiplicity (philosophy), a philosophical concept
* Multiplicity (psychology), having or using multi ...
, then
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
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.
Closure properties
Examples
The sum of two constant-recursive sequences is also constant-recursive. For example, the sum of
and
is
(
), which satisfies the recurrence
. 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. For example, the product of
and
is
(
), which satisfies the recurrence
.
The left-shift sequence
and the right-shift sequence
(with
) are constant-recursive because they satisfy the same recurrence relation. For example, because
is constant-recursive, so is
.
List of operations
In general, constant-recursive sequences are
closed under
In mathematics, a subset of a given set is closed under an operation of the larger set if performing that operation on members of the subset always produces a member of that subset. For example, the natural numbers are closed under addition, but n ...
the following operations, where
denote constant-recursive sequences,
are their generating functions, and
are their orders, respectively.
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
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
(rational, algebraic, real, or complex numbers).
Behavior
Zeros
Despite satisfying a simple local formula, a constant-recursive sequence can 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
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
of
characteristic zero.
Decision problems
The pattern of zeros in a constant-recursive sequence can also be investigated from the perspective of
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
. 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.
[.]
Given such an encoding for sequences
, the following problems can be studied:
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
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to s ...
).
The Skolem-Mahler-Lech theorem would provide answers to some of these questions, except that its proof is
non-constructive
In mathematics, a constructive proof is a method of mathematical proof, proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object. This is in contrast to a non-constructive proof (also ...
. 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.
On the other hand, the exact pattern which repeats after
''is'' computable.
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.
Generalizations
* A
holonomic sequence
In mathematics, and more specifically in Mathematical analysis, analysis, a holonomic function is a smooth function of several variables that is a solution of a system of linear differential equation, linear homogeneous differential equations with ...
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
.
Notes
References
*
Further reading
*
*
Combinatorics
Dynamical systems
Integer sequences
Linear algebra
Recurrence relations
External links
* {{cite web , title= OEIS Index Rec, url=http://oeis.org/wiki/Index_to_OEIS:_Section_Rec
OEIS
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...
index to a few thousand examples of linear recurrences, sorted by order (number of terms) and signature (vector of values of the constant coefficients)