Constant-recursive sequence

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

Definition

An order-d homogeneous linear recurrence with constant coefficients is an equation of the form

s(n) = c_1 s(n-1) + c_2 s(n-2) + \cdots + c_d s(n-d),

where the d coefficients c_1, c_2, \dots, c_d are constants.

A sequence s(0), s(1), s(2), \dots 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.

Equivalently, s(n)_{n \geq 0} is constant-recursive if the set of sequences

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

is contained in a vector space whose dimension is finite.

Examples

Fibonacci sequence

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

F_n = F_{n-1}+F_{n-2}

with initial conditions

F_0 = 0
F_1 = 1.

Explicitly, the recurrence yields the values

F_2 = F_1 + F_0 = 1
F_3 = F_2 + F_1 = 2
F_4 = F_3 + F_2 = 3
F_5 = F_4 + F_3 = 5

etc.

Lucas sequences

The sequence 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ... of Lucas numbers satisfies the same recurrence as the Fibonacci sequence but with initial conditions

L_0 = 2
L_1 = 1.

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

Geometric sequences

The geometric sequence a, a r, a r^2, \dots is constant-recursive, since it satisfies the recurrence s(n) = r s(n - 1) for all n \geq 1.

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 for some d.

Characterization in terms of exponential polynomials

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

x^d - c_1 x^{d-1} - \cdots - c_{d-1} x - c_d

whose coefficients are the same as those of the recurrence. The nth term s(n) of a constant-recursive sequence can be written in terms of the roots of its characteristic polynomial. If the d roots r_1, r_2, \dots, r_d are all distinct, then the nth term of the sequence is

s(n) = k_1 r_1^n + k_2 r_2^n + \cdots + k_d r_d^n

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

For the Fibonacci sequence, the characteristic polynomial is x^2 - x - 1, whose roots \phi = \frac{1 + \sqrt{5}}{2} and \overline{\phi} = \frac{1 - \sqrt{5}}{2} appear in Binet's formula

F_n = \frac{\phi^n-\overline{\phi}^n}{\sqrt 5}.

More generally, if a root r of the characteristic polynomial has multiplicity m, then the term r^n is multiplied by a degree-(m-1) polynomial in n. That is, let r_1, \dots, r_e be the distinct roots of the characteristic polynomial. Then

s(n) = k_1(n) r_1^n + k_2(n) r_2^n + \cdots + k_e(n) r_e^n

where k_i(n) is a polynomial of degree m_i - 1. For instance, if the characteristic polynomial factors as (x-r)^3, with the same root r occurring three times, then the nth term is of the form

s(n) = (a + b n + c n^2) r^n.[1]

Conversely, if there are polynomials k_i(n) such that

s(n) = k_1(n) r_1^n + k_2(n) r_2^n + \cdots + k_e(n) r_e^n,

then s(n)_{n \geq 0} is constant-recursive.

Characterization in terms of rational generating functions

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

The generating function of the Fibonacci sequence is

\frac{x}{1-x-x^2}.

In general, multiplying a generating function by the polynomial

1 - c_1 x^1 - c_2 x^2 - \cdots - c_d x^d

yields a series

\left(s(0) + s(1) x^1 + s(2) x^2 + \cdots \right) \left(1 - c_1 x^1 - c_2 x^2 - \cdots - c_d x^d \right) = \left(b_0 + b_1 x^1 + b_2 x^2 + \cdots\right),

where

b_n = s(n) - c_1 s(n-1) - c_2 s(n-2) - \cdots - c_d s(n-d).

If s(n) satisfies the recurrence relation

s(n) = c_1 s(n-1) + c_2 s(n-2) + \cdots + c_d s(n-d),

then b_n = 0 for all n \geq d. In other words,

\left(s(0) + s(1) x^1 + s(2) x^2 + \cdots \right) \left(1 - c_1 x^1 - c_2 x^2 - \cdots - c_d x^d \right) = \left(b_0 + b_1 x^1 + b_2 x^2 + \cdots + b_{d-1} x^{d-1}\right),

so we obtain the rational function

\sum_{n \geq 0} s(n) x^n = \frac{b_0 + b_1 x^1 + b_2 x^2 + \cdots + b_{d-1} x^{d-1}}{1 - c_1 x^1 - c_2 x^2 - \cdots - c_d x^d}.

In the special case of a periodic sequence satisfying s(n) = s(n-d) for n \geq d, the generating function is

\begin{align}\frac{s(0) + s(1) x^1 + \cdots + s(d-1) x^{d-1}}{1-x^d} =& \left(s(0) + s(1) x^1 + \cdots + s(d-1) x^{d-1}\right) + \left(s(0) + s(1) x^1 + \cdots + s(d-1) x^{d-1}\right) x^d + {}\\& \left(s(0) + s(1) x^1 + \cdots + s(d-1) x^{d-1}\right) x^{2d} + \cdots\end{align}

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

s(n) = c_1 s(n-1) + c_2 s(n-2) + \cdots + c_d s(n-d) + c

can be solved for c to obtain

c = s(n) - c_1 s(n-1) - c_2 s(n-2) - \cdots - c_d s(n-d).

Substituting this into the equation

s(n+1) = c_1 s(n) + c_2 s(n-1) + \cdots + c_d s(n+1-d) + c

shows that s(n) satisfies the homogeneous recurrence

s(n+1) = (c_1 + 1) s(n) + (c_2 - c_1) s(n-1) + \cdots + (c_d  - c_{d-1}) s(n+1-d) - c_d s(n-d)

of order d + 1.

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 k-regular sequence satisfies 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.

Notes

  1. 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.
  2. Martino, Ivan; Martino, Luca (2013-11-14). "On the variety of linear recurrences and numerical semigroups". Semigroup Forum 88 (3): 569–574. doi:10.1007/s00233-013-9551-2. ISSN 0037-1912.

References

External links

This article is issued from Wikipedia - version of the Wednesday, April 13, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.