This site is supported by donations to The OEIS Foundation.

Recurrence

From OeisWiki
Jump to: navigation, search


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
F0 = 0, F1 = 1
. 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
a0 = 0
. (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
xn =
xn  − 1
2
+
1
xn  − 1
, n   ≥   1,
with
x0 = 1
; this has the limit
limn → xn =
2  2
.[4] (See A001601 for the numerators and A051009 for the denominators of
xn
.)

This article is concerned with recurrences with constant coefficients, as opposed to recurrences with nonconstant coefficients.

Contents

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
x  − 1
to
10k
, we get the form
For example, for the first few values of
k
, we have (note that overlapping would occur if powers of 1 had more than
k
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
k
, we have (note that overlapping would occur if powers of 1 had more than
k
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:
a (n) = 2n
.
{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
x  − 1
to
10k
, we get the form
For example, for the first few values of
k
, we have (note that overlapping would occur if powers of 1 had more than
k
digits)
k = 1: 10 / 8 = 1.25 (here

n  = 3
2n
(10k)n
= 0.01
, 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
k
, we have (note that overlapping occurs when powers of 2 have more than
k
digits)
{{mathfont|k = 1: 1 / 8 = 0.125 (here

n  = 3
2n
(10k)n +1
= 0.001
, 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
F (0) = 0
and
F (1) = 1
.
{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
x  − 1
to
10k
, we get the form
For example, for the first few values of
k
, we have (note that overlapping occurs when Fibonacci numbers have more than
k
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
k
, we have (note that overlapping occurs when Fibonacci numbers have more than
k
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
x  − 1
to
10k
, we get the form
For example, for the first few values of
k
, we have (note that overlapping occurs when tribonacci numbers have more than
k
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
k
, we have (note that overlapping occurs when tribonacci numbers have more than
k
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)
k
, is a recurrence of the form

with initial conditions

where

is called the signature. The above recurrence without the
f (n)
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
1 +
⌊  k / 2⌋
coefficients
di (∀i)
are constants. (Note that there are no squared
aj (∀j)
.)
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
k

i  = 0
| ci |
  ≠   0
or
f (n)   ≠   0
and the
1 +
⌊  k / 2⌋
coefficients
di (∀i)
and
ci (∀i)
and are constants. (Note that there are no squared
aj (∀j)
.)

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

  1. “Recurrence relation” in The Penguin Dictionary of Mathematics, Third Edition, edited by David Nelson. Penguin (2003).
  2. “Recurrence relation” in The HarperCollins Dictionary of Mathematics, by E. J. Borowski & J. M. Borwein. HarperCollins (1991).
  3. Peter Tannenbaum & Robert Arnold, Excursions in Modern Mathematics, Third Edition, Chapter 9, “Spiral Growth in Nature,” p. 303. Prentice-Hall (1998).
  4. Steven R. Finch, Mathematical Constants, Section 1.1, “Pythagoras’ Constant,
    2  2
    ” Cambridge University Press (2003).

External links