HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a recurrence relation is an
equation In mathematics, an equation is a formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for example, in F ...
according to which the nth term of a
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter k that is independent of n; this number k is called the ''order'' of the relation. If the values of the first k numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation. In ''linear recurrences'', the th term is equated to a linear function of the k previous terms. A famous example is the recurrence for the Fibonacci numbers, F_n=F_+F_ where the order k is two and the linear function merely adds the two previous terms. This example is a
linear recurrence with constant coefficients In mathematics (including combinatorics, linear algebra, and dynamical systems), a linear recurrence with constant coefficients (also known as a linear recurrence relation or linear difference equation) sets equal to 0 a polynomial that is linear ...
, because the coefficients of the linear function (1 and 1) are constants that do not depend on n. For these recurrences, one can express the general term of the sequence as a
closed-form expression In mathematics, a closed-form expression is a mathematical expression that uses a finite number of standard operations. It may contain constants, variables, certain well-known operations (e.g., + − × ÷), and functions (e.g., ''n''th r ...
of n. As well, linear recurrences with polynomial coefficients depending on n are also important, because many common elementary and special functions have a
Taylor series In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor ser ...
whose coefficients satisfy such a recurrence relation (see holonomic function). Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function of n. The concept of a recurrence relation can be extended to multidimensional arrays, that is,
indexed families In mathematics, a family, or indexed family, is informally a collection of objects, each associated with an index from some index set. For example, a ''family of real numbers, indexed by the set of integers'' is a collection of real numbers, whe ...
that are indexed by
tuple In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
s of
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
s.


Definition

A ''recurrence relation'' is an equation that expresses each element of a
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
as a function of the preceding ones. More precisely, in the case where only the immediately preceding element is involved, a recurrence relation has the form :u_n=\varphi(n, u_)\quad\text\quad n>0, where :\varphi:\mathbb N\times X \to X is a function, where is a set to which the elements of a sequence must belong. For any u_0\in X, this defines a unique sequence with u_0 as its first element, called the ''initial value''. It is easy to modify the definition for getting sequences starting from the term of index 1 or higher. This defines recurrence relation of ''first order''. A recurrence relation of ''order'' has the form :u_n=\varphi(n, u_, u_, \ldots, u_)\quad\text\quad n\ge k, where \varphi: \mathbb N\times X^k \to X is a function that involves consecutive elements of the sequence. In this case, initial values are needed for defining a sequence.


Examples


Factorial

The
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \ ...
is defined by the recurrence relation :n!=n(n-1)!\quad\text\quad n>0, and the initial condition :0!=1. This is an example of a ''linear recurrence with polynomial coefficients'' of order 1, with the simple polynomial :f(n)=n as its only coefficient.


Logistic map

An example of a recurrence relation is the
logistic map The logistic map is a polynomial mapping (equivalently, recurrence relation) of degree 2, often referred to as an archetypal example of how complex, chaotic behaviour can arise from very simple non-linear dynamical equations. The map was popula ...
: :x_ = r x_n (1 - x_n), with a given constant r; given the initial term x_0 each subsequent term is determined by this relation.


Fibonacci numbers

The recurrence of order two satisfied by the Fibonacci numbers is the canonical example of a homogeneous linear recurrence relation with constant coefficients (see below). The Fibonacci sequence is defined using the recurrence :F_n = F_+F_ with
initial condition In mathematics and particularly in dynamic systems, an initial condition, in some contexts called a seed value, is a value of an evolving variable at some point in time designated as the initial time (typically denoted ''t'' = 0). Fo ...
s :F_0 = 0 :F_1 = 1. Explicitly, the recurrence yields the equations :F_2 = F_1 + F_0 :F_3 = F_2 + F_1 :F_4 = F_3 + F_2 etc. We obtain the sequence of Fibonacci numbers, which begins :0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... The recurrence can be solved by methods described below yielding Binet's formula, which involves powers of the two roots of the characteristic polynomial t^2 = t + 1; the
generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary serie ...
of the sequence is the
rational function In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be ...
: \frac.


Binomial coefficients

A simple example of a multidimensional recurrence relation is given by the
binomial coefficient In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s \tbinom, which count the ways of selecting k elements out of a set of n elements. They can be computed by the recurrence relation :\binom=\binom+\binom, with the base cases \tbinom=\tbinom=1. Using this formula to compute the values of all binomial coefficients generates an infinite array called Pascal's triangle. The same values can also be computed directly by a different formula that is not a recurrence, but uses
factorial In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial: \begin n! &= n \times (n-1) \times (n-2) \ ...
s, multiplication and division, not just additions: :\binom=\frac. The binomial coefficients can also be computed with a uni-dimensional recurrence: :\binom n k = \binom n(n-k+1)/k, with the initial value \binom n 0 =1 (The division is not displayed as a fraction for emphasizing that it must be computed after the multiplication, for not introducing fractional numbers). This recurrence is widely used in computers because it does not require to build a table as does the bi-dimensional recurrence, and does involve very large integers as does the formula with factorials (if one uses \binom nk= \binom n, all involved integers are smaller than the final result).


Difference operator and difference equations

The is an operator that maps
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
s to sequences, and, more generally, functions to functions. It is commonly denoted \Delta, and is defined, in functional notation, as :(\Delta f)(x)=f(x+1)-f(x). It is thus a special case of finite difference. When using the index notation for sequences, the definition becomes :(\Delta a)_n= a_ - a_n. The parentheses around \Delta f and \Delta a are generally omitted, and \Delta a_n must be understood as the term of index in the sequence \Delta a, and not \Delta applied to the element a_n. Given
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
a=(a_n)_, the of is \Delta a. The is \Delta^2 a=(\Delta\circ\Delta)a= \Delta(\Delta a). A simple computation shows that :\Delta^2 a_n= a_ - 2a_ + a_n. More generally: the ''th difference'' is defined recursively as \Delta^k=\Delta\circ \Delta^, and one has :\Delta^k a_n = \sum_^k (-1)^t \binom a_. This relation can be inverted, giving :a_ = a_n + \Delta a_n + \cdots + \Delta^k(a_n). A of order is an equation that involves the first differences of a sequence or a function, in the same way as a
differential equation In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, ...
of order relates the first
derivative In mathematics, the derivative of a function of a real variable measures the sensitivity to change of the function value (output value) with respect to a change in its argument (input value). Derivatives are a fundamental tool of calculus. ...
s of a function. The two above relations allow transforming a recurrence relation of order into a difference equation of order , and, conversely, a difference equation of order into recurrence relation of order . Each transformation is the
inverse Inverse or invert may refer to: Science and mathematics * Inverse (logic), a type of conditional sentence which is an immediate inference made from another conditional sentence * Additive inverse (negation), the inverse of a number that, when a ...
of the other, and the sequences that are solution of the difference equation are exactly those that satisfies the recurrence relation. For example, the difference equation :3\Delta^2 a_n + 2\Delta a_n + 7a_n = 0 is equivalent to the recurrence relation :3a_ = 4a_ - 8a_n, in the sense that the two equations are satisfied by the same sequences. As it is equivalent for a sequence to satisfy a recurrence relation or to be the solution of a difference equation, the two terms "recurrence relation" and "difference equation" are sometimes used interchangeably. See Rational difference equation and Matrix difference equation for example of uses of "difference equation" instead of "recurrence relation" Difference equations resemble to differential equations, and this resemblance is often used to mimic methods for solving differentiable equations to apply to solving difference equations, and therefore recurrence relations. Summation equations relate to difference equations as integral equations relate to differential equations. See time scale calculus for a unification of the theory of difference equations with that of differential equations.


From sequences to grids

Single-variable or one-dimensional recurrence relations are about sequences (i.e. functions defined on one-dimensional grids). Multi-variable or n-dimensional recurrence relations are about n-dimensional grids. Functions defined on n-grids can also be studied with partial difference equations.


Solving


Solving linear recurrence relations with constant coefficients


Solving first-order non-homogeneous recurrence relations with variable coefficients

Moreover, for the general first-order non-homogeneous linear recurrence relation with variable coefficients: :a_ = f_n a_n + g_n, \qquad f_n \neq 0, there is also a nice method to solve it: :a_ - f_n a_n = g_n :\frac - \frac = \frac :\frac - \frac = \frac Let :A_n = \frac, Then :A_ - A_n = \frac :\sum_^(A_ - A_m) = A_n - A_0 = \sum_^\frac :\frac = A_0 + \sum_^\frac :a_n = \left(\prod_^ f_k \right) \left(A_0 + \sum_^\frac\right) If we apply the formula to a_ = (1 + h f_) a_n + hg_ and take the limit h \to 0, we get the formula for first order
linear differential equation In mathematics, a linear differential equation is a differential equation that is defined by a linear polynomial in the unknown function and its derivatives, that is an equation of the form :a_0(x)y + a_1(x)y' + a_2(x)y'' \cdots + a_n(x)y^ = b ...
s with variable coefficients; the sum becomes an integral, and the product becomes the exponential function of an integral.


Solving general homogeneous linear recurrence relations

Many homogeneous linear recurrence relations may be solved by means of the
generalized hypergeometric series In mathematics, a generalized hypergeometric series is a power series in which the ratio of successive coefficients indexed by ''n'' is a rational function of ''n''. The series, if convergent, defines a generalized hypergeometric function, wh ...
. Special cases of these lead to recurrence relations for the orthogonal polynomials, and many
special function Special functions are particular mathematical functions that have more or less established names and notations due to their importance in mathematical analysis, functional analysis, geometry, physics, or other applications. The term is defined b ...
s. For example, the solution to :J_=\fracJ_n-J_ is given by :J_n=J_n(z), the
Bessel function Bessel functions, first defined by the mathematician Daniel Bernoulli and then generalized by Friedrich Bessel, are canonical solutions of Bessel's differential equation x^2 \frac + x \frac + \left(x^2 - \alpha^2 \right)y = 0 for an arbitrar ...
, while :(b-n)M_ +(2n-b+z)M_n - nM_=0 is solved by :M_n=M(n,b;z) the
confluent hypergeometric series In mathematics, a confluent hypergeometric function is a solution of a confluent hypergeometric equation, which is a degenerate form of a hypergeometric differential equation where two of the three regular singularities merge into an irregula ...
. Sequences which are the solutions of linear difference equations with polynomial coefficients are called P-recursive. For these specific recurrence equations algorithms are known which find
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exampl ...
, rational or hypergeometric solutions.


Solving first-order rational difference equations

A first order rational difference equation has the form w_ = \tfrac. Such an equation can be solved by writing w_t as a nonlinear transformation of another variable x_t which itself evolves linearly. Then standard methods can be used to solve the linear difference equation in x_t.


Stability


Stability of linear higher-order recurrences

The linear recurrence of order d, :a_n = c_1a_ + c_2a_+\cdots+c_da_, has the characteristic equation :\lambda^d - c_1 \lambda^ - c_2 \lambda^ - \cdots - c_d \lambda^0 =0. The recurrence is
stable A stable is a building in which livestock, especially horses, are kept. It most commonly means a building that is divided into separate stalls for individual animals and livestock. There are many different types of stables in use today; the ...
, meaning that the iterates converge asymptotically to a fixed value, if and only if the
eigenvalues In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denote ...
(i.e., the roots of the characteristic equation), whether real or complex, are all less than
unity Unity may refer to: Buildings * Unity Building, Oregon, Illinois, US; a historic building * Unity Building (Chicago), Illinois, US; a skyscraper * Unity Buildings, Liverpool, UK; two buildings in England * Unity Chapel, Wyoming, Wisconsin, US; a ...
in absolute value.


Stability of linear first-order matrix recurrences

In the first-order matrix difference equation : _t - x^*= A _-x^*/math> with state vector x and transition matrix A, x converges asymptotically to the steady state vector x^* if and only if all eigenvalues of the transition matrix A (whether real or complex) have an
absolute value In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), ...
which is less than 1.


Stability of nonlinear first-order recurrences

Consider the nonlinear first-order recurrence :x_n=f(x_). This recurrence is locally stable, meaning that it converges to a fixed point x^* from points sufficiently close to x^*, if the slope of f in the neighborhood of x^* is smaller than
unity Unity may refer to: Buildings * Unity Building, Oregon, Illinois, US; a historic building * Unity Building (Chicago), Illinois, US; a skyscraper * Unity Buildings, Liverpool, UK; two buildings in England * Unity Chapel, Wyoming, Wisconsin, US; a ...
in absolute value: that is, : , f' (x^*) , < 1. A nonlinear recurrence could have multiple fixed points, in which case some fixed points may be locally stable and others locally unstable; for continuous ''f'' two adjacent fixed points cannot both be locally stable. A nonlinear recurrence relation could also have a cycle of period k for k > 1. Such a cycle is stable, meaning that it attracts a set of initial conditions of positive measure, if the composite function :g(x) := f \circ f \circ \cdots \circ f(x) with f appearing k times is locally stable according to the same criterion: : , g' (x^*) , < 1, where x^* is any point on the cycle. In a
chaotic Chaotic was originally a Danish trading card game. It expanded to an online game in America which then became a television program based on the game. The program was able to be seen on 4Kids TV (Fox affiliates, nationwide), Jetix, The CW4Kid ...
recurrence relation, the variable x stays in a bounded region but never converges to a fixed point or an attracting cycle; any fixed points or cycles of the equation are unstable. See also
logistic map The logistic map is a polynomial mapping (equivalently, recurrence relation) of degree 2, often referred to as an archetypal example of how complex, chaotic behaviour can arise from very simple non-linear dynamical equations. The map was popula ...
, dyadic transformation, and tent map.


Relationship to differential equations

When solving an
ordinary differential equation In mathematics, an ordinary differential equation (ODE) is a differential equation whose unknown(s) consists of one (or more) function(s) of one variable and involves the derivatives of those functions. The term ''ordinary'' is used in contrast ...
numerically Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods t ...
, one typically encounters a recurrence relation. For example, when solving the
initial value problem In multivariable calculus, an initial value problem (IVP) is an ordinary differential equation together with an initial condition which specifies the value of the unknown function at a given point in the domain. Modeling a system in physics or o ...
:y'(t) = f(t,y(t)), \ \ y(t_0)=y_0, with Euler's method and a step size h, one calculates the values :y_0=y(t_0), \ \ y_1=y(t_0+h), \ \ y_2=y(t_0+2h), \ \dots by the recurrence :\, y_ = y_n + hf(t_n,y_n), t_n = t_0 + nh Systems of linear first order differential equations can be discretized exactly analytically using the methods shown in the
discretization In applied mathematics, discretization is the process of transferring continuous functions, models, variables, and equations into discrete counterparts. This process is usually carried out as a first step toward making them suitable for numerica ...
article.


Applications


Mathematical biology

Some of the best-known difference equations have their origins in the attempt to model
population dynamics Population dynamics is the type of mathematics used to model and study the size and age composition of populations as dynamical systems. History Population dynamics has traditionally been the dominant branch of mathematical biology, which has a ...
. For example, the Fibonacci numbers were once used as a model for the growth of a rabbit population. The
logistic map The logistic map is a polynomial mapping (equivalently, recurrence relation) of degree 2, often referred to as an archetypal example of how complex, chaotic behaviour can arise from very simple non-linear dynamical equations. The map was popula ...
is used either directly to model population growth, or as a starting point for more detailed models of population dynamics. In this context, coupled difference equations are often used to model the interaction of two or more
population Population typically refers to the number of people in a single area, whether it be a city or town, region, country, continent, or the world. Governments typically quantify the size of the resident population within their jurisdiction usi ...
s. For example, the
Nicholson–Bailey model The Nicholson–Bailey model was developed in the 1930s to describe the population dynamics of a coupled host-parasitoid system. It is named after Alexander John Nicholson and Victor Albert Bailey. Host-parasite and prey-predator systems can als ...
for a host-
parasite Parasitism is a close relationship between species, where one organism, the parasite, lives on or inside another organism, the host, causing it some harm, and is adapted structurally to this way of life. The entomologist E. O. Wilson h ...
interaction is given by :N_ = \lambda N_t e^ :P_ = N_t(1-e^), with N_t representing the hosts, and P_t the parasites, at time t.
Integrodifference equation In mathematics, an integrodifference equation is a recurrence relation on a function space, of the following form: : n_(x) = \int_ k(x, y)\, f(n_t(y))\, dy, where \\, is a sequence in the function space and \Omega\, is the domain of those functio ...
s are a form of recurrence relation important to spatial
ecology Ecology () is the study of the relationships between living organisms, including humans, and their physical environment. Ecology considers organisms at the individual, population, community, ecosystem, and biosphere level. Ecology overl ...
. These and other difference equations are particularly suited to modeling univoltine populations.


Computer science

Recurrence relations are also of fundamental importance in
analysis of algorithms In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that r ...
. If an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
is designed so that it will break a problem into smaller subproblems ( divide and conquer), its running time is described by a recurrence relation. A simple example is the time an algorithm takes to find an element in an ordered vector with n elements, in the worst case. A naive algorithm will search from left to right, one element at a time. The worst possible scenario is when the required element is the last, so the number of comparisons is n. A better algorithm is called
binary search In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the ...
. However, it requires a sorted vector. It will first check if the element is at the middle of the vector. If not, then it will check if the middle element is greater or lesser than the sought element. At this point, half of the vector can be discarded, and the algorithm can be run again on the other half. The number of comparisons will be given by :c_1=1 :c_n=1+c_ the
time complexity In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
of which will be O(\log_2(n)).


Digital signal processing

In
digital signal processing Digital signal processing (DSP) is the use of digital processing, such as by computers or more specialized digital signal processors, to perform a wide variety of signal processing operations. The digital signals processed in this manner are ...
, recurrence relations can model feedback in a system, where outputs at one time become inputs for future time. They thus arise in infinite impulse response (IIR)
digital filter In signal processing, a digital filter is a system that performs mathematical operations on a sampled, discrete-time signal to reduce or enhance certain aspects of that signal. This is in contrast to the other major type of electronic filter, t ...
s. For example, the equation for a "feedforward" IIR
comb filter In signal processing, a comb filter is a filter implemented by adding a delayed version of a signal to itself, causing constructive and destructive interference. The frequency response of a comb filter consists of a series of regularly space ...
of delay T is: :y_t = (1 - \alpha) x_t + \alpha y_, where x_t is the input at time t, y_t is the output at time t, and \alpha controls how much of the delayed signal is fed back into the output. From this we can see that :y_t = (1 - \alpha) x_t + \alpha ((1-\alpha) x_ + \alpha y_) :y_t = (1 - \alpha) x_t + (\alpha-\alpha^2) x_ + \alpha^2 y_ etc.


Economics

Recurrence relations, especially linear recurrence relations, are used extensively in both theoretical and empirical economics. In particular, in macroeconomics one might develop a model of various broad sectors of the economy (the financial sector, the goods sector, the labor market, etc.) in which some agents' actions depend on lagged variables. The model would then be solved for current values of key variables (
interest rate An interest rate is the amount of interest due per period, as a proportion of the amount lent, deposited, or borrowed (called the principal sum). The total interest on an amount lent or borrowed depends on the principal sum, the interest rate, t ...
, real GDP, etc.) in terms of past and current values of other variables.


See also

* Holonomic sequences * Iterated function * Orthogonal polynomials *
Recursion Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematic ...
*
Recursion (computer science) In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves ...
* Lagged Fibonacci generator * Master theorem (analysis of algorithms) * Circle points segments proof * Continued fraction * Time scale calculus * Combinatorial principles * Infinite impulse response * Integration by reduction formulae *
Mathematical induction Mathematical induction is a method for proving that a statement ''P''(''n'') is true for every natural number ''n'', that is, that the infinitely many cases ''P''(0), ''P''(1), ''P''(2), ''P''(3), ...  all hold. Informal metaphors help ...


References


Footnotes


Bibliography

* * * * *
Thomas H. Cormen Thomas H. Cormen is the co-author of ''Introduction to Algorithms'', along with Charles Leiserson, Ron Rivest, and Cliff Stein. In 2013, he published a new book titled '' Algorithms Unlocked''. He is a professor of computer science at Dartmou ...
, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. '' Introduction to Algorithms'', Second Edition. MIT Press and McGraw-Hill, 1990. . Chapter 4: Recurrences, pp. 62–90. * * * chapter 7. * Chapter 9.1: Difference Equations. * * at EqWorld - The World of Mathematical Equations. * at EqWorld - The World of Mathematical Equations. *


External links

* * * OEIS index to a few thousand examples of linear recurrences, sorted by order (number of terms) and signature (vector of values of the constant coefficients) {{Authority control Algebra Combinatorics