
In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, 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 call ...
of
number
A number is a mathematical object used to count, measure, and label. The most basic 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 can ...
s
is called constant-recursive if it satisfies an equation of the form
:
for all
, where
are
constants. The equation is called a
linear recurrence relation.
The concept is also known as a linear recurrence sequence, linear-recursive sequence, linear-recurrent sequence, or a C-finite sequence.
For example, the
Fibonacci sequence
In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...
:
,
is constant-recursive because it satisfies the linear recurrence
: each number in the sequence is the sum of the previous two.
Other examples include the
power of two
A power of two is a number of the form where is an integer, that is, the result of exponentiation with number 2, two as the Base (exponentiation), base and integer as the exponent. In the fast-growing hierarchy, is exactly equal to f_1^ ...
sequence
, where each number is the sum of twice the previous number, and 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
. All
arithmetic progression
An arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference from any succeeding term to its preceding term remains constant throughout the sequence. The constant difference is called common difference of that ...
s, all
geometric progression
A geometric progression, also known as a geometric sequence, is a mathematical sequence of non-zero numbers where each term after the first is found by multiplying the previous one by a fixed number called the ''common ratio''. For example, the s ...
s, and all
polynomial
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
s are constant-recursive. However, not all sequences are constant-recursive; for example, the
factorial
In mathematics, the factorial of a non-negative denoted is the Product (mathematics), 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 ...
sequence
is not constant-recursive.
Constant-recursive sequences are studied in
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
and the theory of
finite difference
A finite difference is a mathematical expression of the form . Finite differences (or the associated difference quotients) are often used as approximations of derivatives, such as in numerical differentiation.
The difference operator, commonly d ...
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
polynomial roots; 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 r ...
, as the running time of simple
recursive functions; and in the theory of
formal language
In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet".
The alphabet of a formal language consists of symbols that concatenate into strings (also c ...
s, 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 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), divis ...
, term-wise
multiplication
Multiplication is one of the four elementary mathematical operations of arithmetic, with the other ones being addition, subtraction, and division (mathematics), division. The result of a multiplication operation is called a ''Product (mathem ...
, 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 infin ...
.
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. 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, rati ...
, which asks for an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
to determine whether a linear recurrence has at least one zero, is an
unsolved problem in mathematics.
Definition
A constant-recursive sequence is any sequence of
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
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 (for example,
The set of all ...
s,
algebraic number
In mathematics, an algebraic number is a number that is a root of a function, root of a non-zero polynomial in one variable with integer (or, equivalently, Rational number, rational) coefficients. For example, the golden ratio (1 + \sqrt)/2 is ...
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 duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...
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 for ...
s
(written as
as a shorthand) satisfying a formula of the form
for all
for some fixed
coefficient
In mathematics, a coefficient is a Factor (arithmetic), multiplicative factor involved in some Summand, term of a polynomial, a series (mathematics), series, or any other type of expression (mathematics), expression. It may be a Dimensionless qu ...
s
ranging over the same domain as the sequence (integers, rational numbers, algebraic numbers, real numbers, or complex numbers).
The equation is called a
linear recurrence with constant coefficients of order ''d''.
The ''order'' of the sequence is the smallest positive integer
such that the sequence satisfies a recurrence of order ''d'', or
for the everywhere-zero sequence.
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 sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...
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 sequence is an integer sequence named after the mathematician François Édouard Anatole Lucas (1842–1891), who studied both that sequence and the closely related Fibonacci sequence. Individual numbers in the Lucas sequence ar ...
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 rec ...
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 from any succeeding term to its preceding term remains constant throughout the sequence. The constant difference is called common difference of that ...
is constant-recursive of order 2, because it satisfies
. Generalizing this, see
polynomial sequences below.
Geometric progressions
For any
and
, the
geometric progression
A geometric progression, also known as a geometric sequence, is a mathematical sequence of non-zero numbers where each term after the first is found by multiplying the previous one by a fixed number called the ''common ratio''. For example, the s ...
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
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. 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 difference
A finite difference is a mathematical expression of the form . Finite differences (or the associated difference quotients) are often used as approximations of derivatives, such as in numerical differentiation.
The difference operator, commonly d ...
s.
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 over the unary alphabet
over the
semiring
In abstract algebra, a semiring is an algebraic structure. Semirings are a generalization of rings, dropping the requirement that each element must have an additive inverse. At the same time, semirings are a generalization of bounded distribu ...
(which is in fact a
ring
(The) Ring(s) may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
Arts, entertainment, and media Film and TV
* ''The Ring'' (franchise), a ...
, and even a
field) is constant-recursive.
Other examples
The sequences of
Jacobsthal numbers,
Padovan numbers,
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 numbers are constant-recursive.
Non-examples
The
factorial
In mathematics, the factorial of a non-negative denoted is the Product (mathematics), 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 ...
sequence
is not constant-recursive. More generally, every constant-recursive function is asymptotically bounded by an
exponential function (see
#Closed-form characterization) and the factorial sequence grows faster than this.
The
Catalan sequence is not constant-recursive. This is because the
generating function of the Catalan numbers is not 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 ...
(see
#Equivalent definitions).
Equivalent definitions
In terms of matrices
, -style="text-align:center;"
,
A sequence
is constant-recursive of order less than or equal to
if and only if it can be written as
:
where
is a
vector,
is a
matrix
Matrix (: matrices or matrixes) or MATRIX may refer to:
Science and mathematics
* Matrix (mathematics), a rectangular array of numbers, symbols or expressions
* Matrix (logic), part of a formula in prenex normal form
* Matrix (biology), the m ...
, 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
In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a mapping V \to W between two vector spaces that pr ...
that computes
from
, and
the vector