“Recurrence Sequence”的概念、定义、习题解题方法及翻译-数学辞典

单词

Recurrence Sequence

释义

Recurrence Sequence

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

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

(1)

for

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 linearrecurrence 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 arePolynomials of degree

for Positive Integers

, and

. Thenthe 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, soit is impossible for every Rational Number to occur in any finitely generated recurrence sequence. If a recurrencesequence vanishes infinitely often, then it vanishes on an arithmetic progression with a common difference 1 that depends onlyon 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, orin 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, LucasSequence, 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.

随便看

数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。