FACTOID # 18: Alaska spends more money per capita on elementary and secondary education than any other state.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Recurrence relation

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. Mathematics is often defined as the study of topics such as quantity, structure, space, and change. ... See: Recursion Recursively enumerable language Recursively enumerable set Recursive filter Recursive function Recursive set Primitive recursive function This is a disambiguation page â€” a list of pages that otherwise might share the same title. ...

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

$x_{n+1} = r x_n (1 - x_n) ,$

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 GA_googleFillSlot("encyclopedia_square");

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.-1...

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 rn 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...

Consider, for example, a recurrence relation of the form

$a_{n}=Aa_{n-1}+Ba_{n-2}. ,$

Suppose that it has a solution of the form an = rn. Substituting this guess in the recurrence relation, we find:

$r^{n}=Ar^{n-1}+Br^{n-2}. ,$

Dividing through by rn − 2 we get:

$r^2=Ar+B ,$
$r^2-Ar-B=0 ,$

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

$a_n = Clambda_1^n+Dlambda_2^n ,$

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

$a_n = Clambda^n+Dnlambda^n ,$

where constants C and D can be found from the "side conditions" that are often given as a0 = a, a1 = b.

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

Interestingly, the method for solving linear differential equations is similar to the method above — the "intelligent guess" for linear differential equations with constant coefficients is eλx where λ is a complex number that is determined by substituting the guess into the differential equation. 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. ...

$sum_{n=0}^{infin} frac{f^{(n)}(a)}{n!} (x-a)^{n}$

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.

The rule of thumb (for equations in which the polynomial multiplying the first term is non-zero at zero) is that:

y[k] − > f[n + k]

and more generally

xm * y[k] − > n(n − 1)(nm + 1)f[n + km]

Example: The recurrence relationship for the Taylor series coefficients of the equation:

$(x^2 + 3x -4)y^{[3]} -(3x+1)y^{[2]} + 2y = 0,$

is given by

$n(n-1)f[n+1] + 3nf[n+2] -4f[n+3] -3nf[n+1] -f[n+2]+ 2f[n] = 0,$

or

$-4f[n+3] +2nf[n+2] + n(n-4)f[n+1] +2f[n] = 0.,$

This example shows how problems generally solved using the power series solution method taught in normal differential equation classes can be solved in a much easier way.

Example: The differential equation

$ay'' + by' +cy = 0,$

has solution

$y=e^{ax}.,$

The conversion of the differential equation to a difference equation of the Taylor coefficients is

af[n + 2] + bf[n + 1] + cf[n] = 0.

It is easy to see that the nth derivative of eax evaluated at 0 is an

Solving inhomogeneous recurrence relations

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. Another method to solve an inhomogeneous recurrence is the method of symbolic differentiation. For example, consider the following recurrence: In mathematics, the method of undetermined coefficients is an approach to solving certain ordinary differential equations and recurrence relations. ...

$a_{n+1} = a_{n} + 1,$

This is an inhomogeneous recurrence. If we substitute $n mapsto n + 1$, we obtain the recurrence

$a_{n+2} = a_{n+1} + 1,$

Subtracting the original recurrence from this equation yields

$a_{n+2} - a_{n+1} = a_{n+1} - a_{n},$

or equivalently

$a_{n+2} = 2 a_{n+1} - a_{n},$

This is a homogenous recurrence which can be solved by the methods explained above. In general, if a linear recurrence has the form

$a_{n+k} = lambda_{k-1} a_{n+k-1} + lambda_{k-2} a_{n+k-2} + cdots + lambda_1 a_{n+1} + lambda_0 a_{n} + p(n)$

where $lambda_0, lambda_1, dots, lambda_{k-1}$ are constant coefficients and p(n) is the inhomogeneity, then if p(n) is a polynomial with degree r, then this inhomogeneous recurrence can be reduced to a homogenous recurrence by applying the method of symbolic differentiation r times.

Example: Fibonacci numbers

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

$F_{n} = F_{n-1}+F_{n-2} ,$
$F_{0} = 0 ,$
$F_{1} = 1, ,$

whose solution is

$F_n = {phi^n - (1-phi)^n over sqrt{5}}$

where

$phi = {1+sqrt{5} over 2}$

denotes the golden ratio. Therefore, the sequence of Fibonacci numbers is: The golden ratio, also known as the golden proportion, golden mean, golden section, golden number, divine proportion or sectio divina, is an irrational number, approximately 1. ...

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

Relationship to differential equations

When solving an ordinary differential equation numerically, one typically encounters a recurrence relation. For example, when solving the initial value problem In mathematics, and particularly in analysis, an ordinary differential equation (or ODE) is an differential equation that contains functions of only one independent variable, and derivatives in that variable. ... Numerical ordinary differential equations is the part of numerical analysis which studies the numerical solution of ordinary differential equations (ODEs). ... In mathematics, an initial value problem is a statement of a differential equation together with specified value of the unknown function at a given point in the domain of the solution. ...

$y'(t) = f(t,y(t)), qquad y(t_0)=y_0, qquadqquad$

with Euler's method and a step size h, one calculates the values y0 = y(t0), y1 = y(t0 + h), y2 = y(t0 + 2h),... by the recurrence Numerical ordinary differential equations is the part of numerical analysis which studies the numerical solution of ordinary differential equations (ODEs). ...

yn + 1 = yn + hf(tn,yn).

Systems of linear first order differential equations can be discretized exactly analytically using the methods shown in the discretization article. Discretization concerns the process of transferring continuous models and equations into discrete counterparts. ...

In mathematics, a differential equation is an equation in which the derivatives of a function appear as variables. ... A Sierpinski triangle â€”a confined recursion of triangles to form a geometric lattice. ... A Lagged Fibonacci generator (LFG) is an example of a pseudorandom number generator. ... In the analysis of algorithms, the master theorem, which is a specific case of the Akra-Bazzi theorem, provides a cookbook solution in asymptotic terms for recurrence relations of types that occur in practice. ... In geometry, the problem of dividing a circle into areas by means of an inscribed polygon with n sides, in such a way as to maximise the number of areas created by the edges and diagonals, has a solution by an inductive method. ...

Results from FactBites:

 Recurrence relation - definition of Recurrence relation in Encyclopedia (477 words) 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. 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. This is known as the characteristic equation of the recurrence relation.
More results at FactBites »

Share your thoughts, questions and commentary here