Constant-recursive sequence: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
→‎Other examples: add another example
→‎Definition: for now: make definition precise and comment on eventually-periodic
Line 4: Line 4:


==Definition==
==Definition==
An order-''d'' '''homogeneous linear recurrence with constant coefficients''' is an equation of the form
An order-''d'' '''homogeneous [[linear difference equation|linear recurrence relation]]''' is an equation of the form
:<math>s(n) = c_1 s(n-1) + c_2 s(n-2) + \dots + c_d s(n-d),</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 constants.
where the ''d'' coefficients <math>c_1, c_2, \dots, c_d</math> are [[Constant (mathematics)|constants]]. The coefficients are typically taken to range over the [[integer]]s, [[rational number]]s, [[algebraic number]]s, [[real number]]s, or [[complex number]]s.


A sequence <math>s(0), s(1), s(2), \dots</math> is a '''constant-recursive sequence''' if there is an order-''d'' homogeneous linear recurrence with constant coefficients that it satisfies for all <math>n \geq d</math>.
A sequence <math>s(0), s(1), s(2), \dots</math> (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 <math>n \geq d</math>. Note that this definition allows eventually-periodic sequences such as <math>1, 0, 0, 0, \ldots</math> and <math>0, 1, 0, 0, \ldots</math>, which are disallowed by some authors.<ref>{{Cite book|last=Kauers|first=Manuel|url=https://books.google.com/books?id=BPeODAEACAAJ&newbks=0&hl=en|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}}</ref> These sequences can be disallowed by requiring that <math>c_d \ne 0</math>.


Equivalently, <math>s(n)_{n \geq 0}</math> is constant-recursive if the set of sequences
Equivalently, <math>s(n)_{n \geq 0}</math> is constant-recursive if the set of sequences
:<math>\{s(n + r)_{n \geq 0} : r \geq 0\}</math>
:<math>\{s(n + r)_{n \geq 0} : r \geq 0\}</math>
is contained in a [[vector space]] whose dimension is finite.
is contained in a [[vector space]] whose dimension is finite.

The ''order'' of a constant-recursive sequence is the smallest <math>d</math> such that the sequence satisfies an order-''d'' homogeneous linear recurrence. [[Linear difference equation|Nonhomogenous linear recurrence relations]] can be allowed without changing the set of constant-recursive sequences, but the definition of order would change.


==Examples==
==Examples==

Revision as of 01:52, 8 November 2021

In mathematics, a constant-recursive sequence, C-finite sequence, or linear recurrence sequence is a sequence satisfying a linear recurrence with constant coefficients.

Definition

An order-d homogeneous linear recurrence relation is an equation of the form

where the d coefficients are constants. The coefficients are typically taken to range over the integers, rational numbers, algebraic numbers, real numbers, or complex numbers.

A sequence (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 . Note that this definition allows eventually-periodic sequences such as and , which are disallowed by some authors.[1] These sequences can be disallowed by requiring that .

Equivalently, is constant-recursive if the set of sequences

is contained in a vector space whose dimension is finite.

The order of a constant-recursive sequence is the smallest such that the sequence satisfies an order-d homogeneous linear recurrence. Nonhomogenous linear recurrence relations can be allowed without changing the set of constant-recursive sequences, but the definition of order would change.

Examples

Fibonacci sequence

The sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... of Fibonacci numbers satisfies the recurrence

with initial conditions

Explicitly, the recurrence yields the values

etc.

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

More generally, every Lucas sequence is a constant-recursive sequence.

Geometric sequences

The geometric sequence is constant-recursive, since it satisfies the recurrence for all .

Eventually periodic sequences

A sequence that is eventually periodic with period length is constant-recursive, since it satisfies for all for some .

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 , with coefficients given by the corresponding element of the binomial transform.[2] 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.[citation needed] Each individual equation may also be verified by substituting the degree-d polynomial

where the coefficients are symbolic. 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.

Other examples

The sequences of Jacobsthal numbers, Padovan numbers, Pell numbers, and Perrin numbers are constant-recursive.

Characterization in terms of exponential polynomials

The characteristic polynomial (or "auxiliary polynomial") of the recurrence is the polynomial

whose coefficients are the same as those of the recurrence. The nth term of a constant-recursive sequence can be written in terms of the roots of its characteristic polynomial. If the d roots are all distinct, then the nth term of the sequence is

where the coefficients ki are constants that can be determined from the initial conditions.

For the Fibonacci sequence, the characteristic polynomial is , whose roots and appear in Binet's formula

More generally, if a root r of the characteristic polynomial has multiplicity m, then the term is multiplied by a degree- polynomial in n. That is, let be the distinct roots of the characteristic polynomial. Then

where is a polynomial of degree . For instance, if the characteristic polynomial factors as , with the same root r occurring three times, then the nth term is of the form

[3]

Conversely, if there are polynomials such that

then is constant-recursive.

Characterization in terms of rational generating functions

A sequence is constant-recursive precisely when its generating function

is a rational function. 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 generating function of the Fibonacci sequence is

In general, multiplying a generating function by the polynomial

yields a series

where

If satisfies the recurrence relation

then for all . In other words,

so we obtain the rational function

In the special case of a periodic sequence satisfying for , the generating function is

by expanding the geometric series.

The generating function of the Catalan numbers is not a rational function, which implies that the Catalan numbers do not satisfy a linear recurrence with constant coefficients.

Closure properties

The termwise addition or multiplication of two constant-recursive sequences is again constant-recursive. This follows from the characterization in terms of exponential polynomials.

The Cauchy product of two constant-recursive sequences is constant-recursive. This follows from the characterization in terms of rational generating functions.

Sequences satisfying non-homogeneous recurrences

A sequence satisfying a non-homogeneous linear recurrence with constant coefficients is constant-recursive.

This is because the recurrence

can be solved for to obtain

Substituting this into the equation

shows that satisfies the homogeneous recurrence

of order .

Generalizations

A natural generalization is obtained by relaxing the condition that the coefficients of the recurrence are constants. If the coefficients are allowed to be polynomials, then one obtains holonomic sequences.

A -regular sequence satisfies 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

  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. ^ Boyadzhiev, Boyad (2012). "Close Encounters with the Stirling Numbers of the Second Kind" (PDF). Math. Mag. 85: 252–266.
  3. ^ 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.
  4. ^ 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.

References

See also

External links

  • "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)