TOPICS
Search

Recurrence Equation


A recurrence equation (also called a difference equation) is the discrete analog of a differential equation. A difference equation involves an integer function f(n) in a form like

 f(n)-f(n-1)=g(n),
(1)

where g is some integer function. The above equation is the discrete analog of the first-order ordinary differential equation

 f^'(x)=g(x).
(2)

Examples of difference equations often arise in dynamical systems. Examples include the iteration involved in the Mandelbrot and Julia set definitions,

 f(n+1)=f(n)^2+c,
(3)

with c a constant, as well as the logistic equation

 f(n+1)=rf(n)[1-f(n)],
(4)

with r a constant. Perhaps the most famous example of a recurrence relation is the one defining the Fibonacci numbers,

 F_n=F_(n-2)+F_(n-1)
(5)

for n>=3 and with F_1=F_2=1.

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.

Let

 s(X)=product_(i=1)^m(1-alpha_iX)^(n_i)=1-s_1X-...-s_nX^n,
(6)

where the generalized power sum a(h) for h=0, 1, ... is given by

 a(h)=sum_(i=1)^mA_i(h)alpha_i^h,
(7)

with distinct nonzero roots alpha_i, coefficients A_i(h) which are polynomials of degree n_i-1 for positive integers n_i, and i in [1,m]. Then the sequence {a_h} with a_h=a(h) satisfies the recurrence relation

 a_(h+n)=s_1a_(h+n-1)+...+s_na_h
(8)

(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 l 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 mu(n) be a bound so that a nondegenerate integer recurrence sequence of order n takes the value zero at least mu(n) times. Then mu(2)=1, mu(3)=6, and mu(4)>=9 (Myerson and van der Poorten 1995). The maximal case for mu(3) is

 a_(n+3)=2a_(n+2)-4a_(n+1)+4a_n
(9)

with

 a_0=a_1=0
(10)
 a_2=1.
(11)

The zeros are

 a_0=a_1=a_4=a_6=a_(13)=a_(52)=0
(12)

(Beukers 1991).


See also

Argument Addition Relation, Argument Multiplication Relation, Binet Forms, Binet's Fibonacci Number Formula, Clenshaw Recurrence Formula, Difference-Differential Equation, Fast Fibonacci Transform, Fibonacci Number, Finite Difference, Indicial Equation, Linear Recurrence Equation, Lucas Sequence, Ordinary Differential Equation, Quadratic Recurrence Equation, Quotient-Difference Table, Reflection Relation, Translation Relation, Skolem-Mahler-Lech Theorem

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 q-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. Difference Equations and Inequality: Theory, Methods, and Applications, 2nd ed., rev. exp. New York: Dekker, 2000.Batchelder, P. M. An Introduction to Linear Difference Equations. New York: Dover, 1967.Bellman, R. E. and Cooke, K. L. Differential-Difference Equations. New York: Academic Press, 1963.Beukers, F. "The Zero-Multiplicity of Ternary Recurrences." Composito Math. 77, 165-177, 1991.Beyer, W. H. "Finite Differences." CRC Standard Mathematical Tables, 28th ed. Boca Raton, FL: CRC Press, pp. 429-460, 1988.Birkhoff, G. D. "General Theory of Linear Difference Equations." Trans. Amer. Math. Soc. 12, 243-284, 1911.Brand, L. Differential and Difference Equations. New York: Wiley, 1966.Fulford, G.; Forrester, P.; and Jones, A. Modelling with Differential and Difference Equations. New York: Cambridge University Press, 1997.Goldberg, S. Introduction to Difference Equations, with Illustrative Examples from Economics, Psychology, and Sociology. New York: Dover, 1986.Greene, D. H. and Knuth, D. E. Mathematics for the Analysis of Algorithms, 3rd ed. Boston, MA: Birkhäuser, 1990.Levy, H. and Lessman, F. Finite Difference Equations. New York: Dover, 1992.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 Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 172-178, 1992.Richtmyer, R. D. and Morton, K. W. Difference Methods for Initial-Value Problems, 2nd ed. New York: Interscience Publishers, 1967.Riordan, J. An Introduction to Combinatorial Analysis. New York: Wiley, 1980.Sloane, N. J. A. and Plouffe, S. "Recurrences and Generating Functions" and "Other Methods for Hand Analysis." §2.4 and 2.6 in The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, pp. 9-10 and 13-18, 1995.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. Computations with Recurrence Relations. Boston, MA: Pitman, 1984.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 128-131, 2002.

Referenced on Wolfram|Alpha

Recurrence Equation

Cite this as:

Weisstein, Eric W. "Recurrence Equation." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RecurrenceEquation.html

Subject classifications