## Recurrence Sequence

A sequence of numbers generated by a Recurrence Relation is called a recurrence sequence. Perhaps the most famous recurrence sequence is the Fibonacci Numbers.

If a sequence with is described by a two-term linear recurrence relation of the form

 (1)

for and and constants, then the closed form for is given by
 (2)

where and are the Roots of the Quadratic Equation
 (3)

 (4) (5)

The general second-order linear recurrence

 (6)

for constants and with arbitrary and has terms

Dropping , , and , this can be written

which is simply Pascal's Triangle on its side. An arbitrary term can therefore be written as

 (7) (8)

The general linear third-order recurrence

 (9)

has solution

 (10)
where , , and are the roots of the polynomial

 (11)

A Quotient-Difference Table eventually yields a line of 0s Iff the starting sequence is defined by a linear recurrence relation.

A linear second-order recurrence

 (12)

can be solved rapidly using a rate doubling,''
 (13)

rate tripling''
 (14)

or in general, rate -tupling'' formula
 (15)

where
 (16) (17) (18) (19)

(here, is a Chebyshev Polynomial of the First Kind) and
 (20) (21) (22) (23)

(Beeler et al. 1972, Item 14).

Let

 (24)

where the generalized Power sum for , 1, ... is given by
 (25)

with distinct Nonzero roots , Coefficients which are Polynomials of degree for Positive Integers , and . Then the sequence with satisfies the Recurrence Relation
 (26)

(Meyerson and van der Poorten 1995).

The terms in a general recurrence sequence belong to a finitely generated Ring over the Integers, so it is impossible for every Rational Number to occur in any finitely generated recurrence sequence. If a recurrence sequence vanishes infinitely often, then it vanishes on an arithmetic progression with a common difference 1 that depends only on the roots. The number of values that a recurrence sequence can take on infinitely often is bounded by some Integer that depends only on the roots. There is no recurrence sequence in which each Integer occurs infinitely often, or in which every Gaussian Integer occurs (Myerson and van der Poorten 1995).

Let be a bound so that a nondegenerate Integer recurrence sequence of order takes the value zero at least times. Then , , and (Myerson and van der Poorten 1995). The maximal case for is

 (27)

with
 (28)

 (29)

The zeros are
 (30)

(Beukers 1991).

See also Binet Forms, Binet's Formula, Fast Fibonacci Transform, Fibonacci Sequence, Lucas Sequence, Quotient-Difference Table, Skolem-Mahler-Lerch Theorem

References

Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, Feb. 1972.

Beukers, F. The Zero-Multiplicity of Ternary Recurrences.'' Composito Math. 77, 165-177, 1991.

Myerson, G. and van der Poorten, A. J. Some Problems Concerning Recurrence Sequences.'' Amer. Math. Monthly 102, 698-705, 1995.

© 1996-9 Eric W. Weisstein
1999-05-25