A recurrence equation (also called a difference equation) is the discrete analog of a
differential equation. A difference
equation involves an integer function in a form like
is some integer function. The above equation
is the discrete analog of the first-order
ordinary differential equation
Examples of difference equations often arise in
dynamical systems. Examples include the iteration involved in the Mandelbrot
and Julia set definitions,
a constant, as well as the logistic equation
a constant. Perhaps the most famous example of a recurrence relation is the one defining
the Fibonacci numbers,
and with .
Recurrence equations can be solved using
[ RSolve eqn, a[ n], n]. The solutions to a linear
recurrence equation can be computed straightforwardly, but quadratic
recurrence equations are not so well understood.
The sequence generated by a recurrence relation is called a recurrence sequence.
where the generalized
power sum for , 1, ... is given by
nonzero roots , coefficients which are polynomials
for positive integers , and . Then the sequence with satisfies the recurrence
(Myerson 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).
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
The zeros are
See also Argument Addition Relation
Argument Multiplication Relation
Fibonacci Number Formula
Fast Fibonacci Transform
Explore with Wolfram|Alpha
References Abramov, S. A. "Rational Solutions of Linear Differential and Difference Equations with Polynomial Coefficients." USSR Comput. Meths.
Math. Phys. 29, 7-12, 1989. Abramov, S. A. "Rational
Solutions of Linear Difference and -Difference Equations with Polynomial Coefficients." Proc.
ISSAC' 95, 285-289, 1995. Abramov, S. A.; Bronstein, M.; and
Petkovšek, M. "On Polynomial Solutions of Linear Operator Equations."
Proc. ISSAC' 95, 290-296, 1995. Agarwal, R. P.
New York: Dekker, 2000. Difference
Equations and Inequality: Theory, Methods, and Applications, 2nd ed., rev. exp. Batchelder, P. M. New York: Dover, 1967. An
Introduction to Linear Difference Equations. Bellman,
R. E. and Cooke, K. L. New York: Academic Press, 1963. Differential-Difference
Equations. Beukers, F. "The
Zero-Multiplicity of Ternary Recurrences." Composito Math. 77,
165-177, 1991. Beyer, W. H. "Finite Differences." Boca Raton, FL: CRC Press, pp. 429-460,
Standard Mathematical Tables, 28th ed. Birkhoff, G. D. "General Theory of Linear Difference
Equations." Trans. Amer. Math. Soc. 12, 243-284, 1911. Brand,
L. New York: Wiley, 1966. Differential
and Difference Equations. Fulford, G.;
Forrester, P.; and Jones, A. New York: Cambridge University
Press, 1997. Modelling
with Differential and Difference Equations. Goldberg, S. New York: Dover, 1986. Introduction
to Difference Equations, with Illustrative Examples from Economics, Psychology, and
Sociology. Greene, D. H. and Knuth,
D. E. Boston, MA: Birkhäuser, 1990. Mathematics
for the Analysis of Algorithms, 3rd ed. Levy,
H. and Lessman, F. New York: Dover, 1992. Finite
Difference Equations. Myerson, G. and
van der Poorten, A. J. "Some Problems Concerning Recurrence Sequences."
Amer. Math. Monthly 102, 698-705, 1995. Press, W. H.;
Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Recurrence
Relations and Clenshaw's Recurrence Formula." §5.5 in Cambridge, England:
Cambridge University Press, pp. 172-178, 1992. Numerical
Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Richtmyer, R. D.
and Morton, K. W. New York: Interscience Publishers,
Methods for Initial-Value Problems, 2nd ed. Riordan, J. New York: Wiley, 1980. An
Introduction to Combinatorial Analysis. Sloane,
N. J. A. and Plouffe, S. "Recurrences and Generating Functions"
and "Other Methods for Hand Analysis." §2.4 and 2.6 in San Diego, CA: Academic Press, pp. 9-10
and 13-18, 1995. The
Encyclopedia of Integer Sequences. van Hoeij, M. Rational Solutions of Linear Difference
Equations." Proc. ISSAC' 98, 120-123, 1998. Weisstein, E. W.
"Books about Difference Equations." http://www.ericweisstein.com/encyclopedias/books/DifferenceEquations.html. Wimp,
J. Boston, MA: Pitman, 1984. Computations
with Recurrence Relations. Wolfram,
S. Champaign, IL: Wolfram Media, pp. A
New Kind of Science. 128-131,
2002. Referenced on Wolfram|Alpha Recurrence Equation
Cite this as:
Weisstein, Eric W. "Recurrence Equation."
From --A Wolfram Web Resource. MathWorld https://mathworld.wolfram.com/RecurrenceEquation.html