This article needs more work.
Please help by expanding it!
A
recurrence relation (also called
recursive relation,
[1] difference equation[2] or
recursive definition[3]) is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms. The
Fibonacci sequence is the classic example of a recurrence relation:
Fn = Fn − 1 + Fn − 2, n ≥ 2, |
with
.
Recurrence relations can also be used to calculate some sequences that are usually
computed nonrecursively, e.g. via a
closed-form formula. The
oblong numbers (see
A002378), for example, are defined (and usually computed) as
an = n × (n + 1) = n 2 + n, n ≥ 0; |
but since we have
an − 1 = (n − 1) × n = n 2 − n, n ≥ 1, |
we can trivially obtain the recursive definition
an = an − 1 + (an − an − 1) = an − 1 + 2 n, n ≥ 1, |
(hence
difference equation) with
. (Conversely, sequences computed by
linear recurrence relations can have their values computed directly, as is the case for the Fibonacci numbers with
Binet’s closed-form formula.)
Of course recurrence relations are not limited in application to sequences of integers. A
sequence of rational values that quickly converges (e.g.
convergents of a continued fraction) to the
square root of two (
Pythagoras’ constant, the original
irrational number) is given by the recurrence relation
with
; this has the limit
.
[4] (See
A001601 for the numerators and
A051009 for the denominators of
.)
This article is concerned with recurrences with constant coefficients, as opposed to recurrences with nonconstant coefficients.
Recurrences with constant coefficients
Linear recurrences with constant coefficients
- Main article page: Linear recurrence relations with constant coefficients
Cf. Index entries for sequences related to linear recurrences with constant coefficients.
Homogeneous linear recurrences with constant coefficients
- Main article page: Homogeneous linear recurrence relations with constant coefficients
A homogeneous linear recurrence with constant coefficients, of order (degree) , is a recurrence of the form
with initial conditions
where
is called the signature.
Equivalently, it may also be expressed as an equation of the form
-
Homogeneous linear recurrences (of order 1) with constant coefficients
Powers of 1
A000012 The simplest sequence of positive numbers: the all 1’s sequence.
-
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...}
From the generating function of powers of 1 (where in the second version the denominator has the form of the recurrence)
and setting
to
, we get the form
For example, for the first few values of
, we have (note that overlapping would occur if powers of
1 had more than
digits)
- k = 1: 10 / 9 = 1.11111111111111111111111111111...
- k = 2: 100 / 99 = 1.0101010101010101010101010101...
- k = 3: 1000 / 999 = 1.001001001001001001001001001...
- k = 4: 10000 / 9999 = 1.00010001000100010001000100...
A variant of the above is
For example, for the first few values of
, we have (note that overlapping would occur if powers of
1 had more than
digits)
- k = 1: 1 / 9 = 0.111111111111111111111111111111... (A000012)
- k = 2: 1 / 99 = 0.010101010101010101010101010101... (A000035)
- k = 3: 1 / 999 = 0.001001001001001001001001001001...
- k = 4: 1 / 9999 = 0.000100010001000100010001000100...
Powers of 2
A000079 Powers of
2:
.
-
{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, ...}
From the generating function of powers of 2 (where in the second version the denominator has the form of the recurrence)
and setting
to
, we get the form
For example, for the first few values of
, we have (note that overlapping would occur if powers of
1 had more than
digits)
- k = 1: 10 / 8 = 1.25 (here , and 1 + 2 / 10 + 4 / 100 = (100 + 20 + 4) / 100)
- k = 2: 100 / 98 = 1.0204081632653061224489795918...
- k = 3: 1000 / 998 = 1.002004008016032064128256513...
- k = 4: 10000 / 9998 = 1.00020004000800160032006401...
A variant of the above is
For example, for the first few values of
, we have (note that overlapping occurs when powers of
2 have more than
digits)
- {{mathfont|k = 1: 1 / 8 = 0.125 (here , and 1 / 10 + 2 / 100 + 4 / 1000 = (100 + 20 + 4) / 1000)
- k = 2: 1 / 98 = 0.010204081632653061224489795918... (A021102)
- k = 3: 1 / 998 = 0.001002004008016032064128256513... (A022002)
- k = 4: 1 / 9998 = 0.000100020004000800160032006401...
Homogeneous linear recurrences (of order 2) with constant coefficients
Fibonacci sequence
- Main article page: Fibonacci numbers
A000045 Fibonacci numbers:
F (n) = F (n − 1) + F (n − 2) |
with
and
.
-
{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, ...}
The generating function of the Fibonacci numbers is
Rewriting the generating function as (which shows the form of the recurrence in the denominator)
and setting
to
, we get the form
-
For example, for the first few values of
, we have (note that overlapping occurs when Fibonacci numbers have more than
digits)
- k = 1: 10 / 89 = 0.11235955056179775280898876404...
- k = 2: 100 / 9899 = 0.010102030508132134559046368320...
- k = 3: 1000 / 998999 = 0.0010010020030050080130210340550...
- k = 4: 10000 / 99989999 = 0.00010001000200030005000800130021...
A variant of the above is
For example, for the first few values of
, we have (note that overlapping occurs when Fibonacci numbers have more than
digits)
- k = 1: 1 / 89 = 0.011235955056179775280898876404... (A021093)
- k = 2: 1 / 9899 = 0.00010102030508132134559046368320...
- k = 3: 1 / 998999 = 0.0000010010020030050080130210340550...
- k = 4: 1 / 99989999 = 0.000000010001000200030005000800130021...
Homogeneous linear recurrences (of order 3) with constant coefficients
Tribonacci sequence
- Main article page: Tribonacci numbers
A000073 Tribonacci numbers:
a (n) = a (n − 1) + a (n − 2) + a (n − 3) |
with
a (0) = a (1) = 0, a (2) = 1 |
.
-
{0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, 15902591, 29249425, ...}
The generating function of the tribonacci numbers is
Rewriting the generating function as (which shows the form of the recurrence in the denominator)
and setting
to
, we get the form
For example, for the first few values of
, we have (note that overlapping occurs when tribonacci numbers have more than
digits)
- k = 1: 10 / 889 = 0.011248593925759280089988751406...
- k = 2: 100 / 989899 = 0.00010102040713244482517913443694...
- k = 3: 1000 / 998998999 = 0.0000010010020040070130240440811492...
- k = 4: 10000 / 999899989999 = 0.000000010001000200040007001300240044...
A variant of the above is
For example, for the first few values of
, we have (note that overlapping occurs when tribonacci numbers have more than
digits)
- k = 1: 1 / 889 = 0.0011248593925759280089988751406... (A021893)
- k = 2: 1 / 989899 = 0.0000010102040713244482517913443694...
- k = 3: 1 / 998998999 = 0.0000000010010020040070130240440811492...
- k = 4: 1 / 999899989999 = 0.0000000000010001000200040007001300240044...
Non-homogeneous linear recurrences with constant coefficients
- Main article page: Non-homogeneous linear recurrence relations with constant coefficients
A non-homogeneous linear recurrence with constant coefficients, of order (degree)
, is a recurrence of the form
with initial conditions
where
is called the signature. The above recurrence without the
term is called the
associated homogeneous recurrence.
Equivalently, it may be expressed as an equation of the form
Non-homogeneous linear recurrences (of order 1) with constant coefficients
Examples:
Non-homogeneous linear recurrences (of order 2) with constant coefficients
Examples:
Quadratic recurrences with constant coefficients
- Main article page: Quadratic recurrence relations with constant coefficients
Bilinear recurrence relations with constant coefficients
- Main article page: Bilinear recurrence relations with constant coefficients
Homogeneous bilinear recurrence relations with constant coefficients
A homogeneous bilinear recurrence relation with constant coefficients is an equation of the form
where the
coefficients
are constants. (Note that there are no squared
.)
Non-homogeneous bilinear recurrence relations with constant coefficients
A non-homogeneous bilinear recurrence relation with constant coefficients is an equation of the form
where either
or
and the
coefficients
and
and are constants. (Note that there are no squared
.)
Homogeneous quadratic recurrences with constant coefficients
- Main article page: Homogeneous quadratic recurrence relations with constant coefficients
Homogeneous quadratic recurrences (of order 1) with constant coefficients
Examples:
Homogeneous quadratic recurrences (of order 2) with constant coefficients
Examples:
Non-homogeneous quadratic recurrences with constant coefficients
- Main article page: Non-homogeneous quadratic recurrence relations with constant coefficients
Non-homogeneous quadratic recurrences (of order 1) with constant coefficients
Examples:
Non-homogeneous quadratic recurrences (of order 2) with constant coefficients
Examples:
Cubic recurrences with constant coefficients
- Main article page: Cubic recurrence relations with constant coefficients
Homogeneous cubic recurrences with constant coefficients
Homogeneous cubic recurrences (of order 1) with constant coefficients
Examples:
Homogeneous cubic recurrences (of order 2) with constant coefficients
Examples:
Non-homogeneous cubic recurrences with constant coefficients
Non-homogeneous cubic recurrences (of order 1) with constant coefficients
Examples:
Non-homogeneous cubic recurrences (of order 2) with constant coefficients
Examples:
See also
Notes
- ↑ “Recurrence relation” in The Penguin Dictionary of Mathematics, Third Edition, edited by David Nelson. Penguin (2003).
- ↑ “Recurrence relation” in The HarperCollins Dictionary of Mathematics, by E. J. Borowski & J. M. Borwein. HarperCollins (1991).
- ↑ Peter Tannenbaum & Robert Arnold, Excursions in Modern Mathematics, Third Edition, Chapter 9, “Spiral Growth in Nature,” p. 303. Prentice-Hall (1998).
- ↑ Steven R. Finch, Mathematical Constants, Section 1.1, “Pythagoras’ Constant, ” Cambridge University Press (2003).
External links