Recurrent redirects here; for the meaning of "recurrent" in CHR airplay, see Recurrent rotation. Wikipedia does not yet have an article with this exact name. ... Recurrent rotation refers to a song still getting frequent airplay on a CHR station after several months. ...

In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. History Main article: History of mathematics In addition to recognizing how to count concrete objects, prehistoric peoples also recognized how to count abstract quantities, like time -- days, seasons, years. ... See: Recursion Recursive function Recursive set Recursively enumerable set Recursively enumerable language Primitive recursive function This is a disambiguation page — a navigational aid which lists other pages that might otherwise share the same title. ...

For example (the logistic map): The logistic map is a polynomial mapping, often cited as an archetypical example of how complex, chaotic behaviour can arise from very simple non-linear dynamical equations. ...

Some simply defined recurrence relations can have very complex (chaotic) behaviours and are sometimes studied by physicists and mathematicians in a field of mathematics known as nonlinear analysis.

Solving a recurrence relation means obtaining a non-recursive function of n.

Linear homogeneous recurrence relations with constant coefficients

The term linear means that each term of the sequence is defined as a linear function of the preceding terms. The coefficients and the constants may depend on n, even non-linearly.

A special case is when the coefficients do not depend on n.

Homogeneous means that the constant term of the relation is zero. In mathematics, homogeneous has a variety of meanings. ...

In order to obtain a unique solution to the linear recurrence there must be some initial conditions, as the first number in the sequence can not depend on other numbers in the sequence and must be set to some value.

Solving linear recurrence relations

Solutions to recurrence relations are found by systematic means, often by using generating functions (formal power series) or by noticing the fact that rⁿ is a solution for particular values of r. In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ... In mathematics, formal power series are devices that make it possible to employ much of the analytical machinery of power series in settings that do not have natural notions of convergence. They are also useful to compactly describe sequences and to find closed formulas for recursively defined sequences; this is...

For recurrence relations in the form:

we have the solution rⁿ:

Dividing through by r^{n − 2} we get:

This is known as the characteristic equation of the recurrence relation. Solve for r to obtain the two roots λ₁,λ₂, and if these roots are distinct, we have the solution

while if they are identical (when A²+4B=0), we have

where C and D are constants.

Additionally, if the equation is of the form a_n = Aa_{n − 1} + B you can substitute 2 for n and get r² = Ar + B as above. The constants C and D can be found from the "side conditions" that are often given as a₀ = a, a₁ = b.

Different solutions are obtained depending on the nature of the roots of the characteristic equation.

If the recurrence is inhomogeneous, a particular solution can be found by the method of undetermined coefficients and the solution is the sum of the solution of the homogeneous and the particular solutions.

Interestingly, the method for solving linear differential equations is similar to the method above — the "intelligent guess" for linear differential equations is e^x. In mathematics, a differential equation is an equation in which the derivatives of a function appear as variables. ...

This is not a coincidence. If you consider the Taylor series of the solution to a linear differential equation: As the degree of the taylor series rises, it approaches the correct function. ...

you see that the coefficients of the series are given by the n-th derivative of f(x) evaluated at the point a. The differential equation provides a linear difference equation relating these coefficients.

This equivalence can be used to quickly solve for the recurrence relationship for the coefficients in the power series solution of a linear differential equation.

Example: Fibonacci numbers

The Fibonacci numbers are defined using a linear recurrence relation: In mathematics, the Fibonacci numbers form a sequence defined recursively by: In words: you start with 0 and 1, and then produce the next Fibonacci number by adding the two previous Fibonacci numbers. ...

and has solution (letting be the golden ratio) The golden ratio is an irrational number, approximately 1. ...

The initial conditions are:

Therefore, the sequence of Fibonacci numbers is:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

Related topics

• recursion
• Master theorem
• Circle points segments proof