This site is supported by donations to The OEIS Foundation.

Recurrence

From OeisWiki
(Redirected from Recurrence relation)
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: 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 but since we have we can trivially obtain the recursive definition (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.

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 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)

= 1: 10 / 9 = 1.11111111111111111111111111111...
= 2: 100 / 99 = 1.0101010101010101010101010101...
= 3: 1000 / 999 = 1.001001001001001001001001001...
= 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)

= 1: 1 / 9 = 0.111111111111111111111111111111... (A000012)
= 2: 1 / 99 = 0.010101010101010101010101010101... (A000035)
= 3: 1 / 999 = 0.001001001001001001001001001001...
= 4: 1 / 9999 = 0.000100010001000100010001000100...
Powers of 2


A000079 Powers of 2: a(n) = 2^n.

{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)

= 1: 10 / 8 = 1.25 (here = 0.01, and 1 + 2 / 10 + 4 / 100 = (100 + 20 + 4) / 100)
= 2: 100 / 98 = 1.0204081632653061224489795918...
= 3: 1000 / 998 = 1.002004008016032064128256513...
= 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)

= 1: 1 / 8 = 0.125 (here = 0.001, and 1 / 10 + 2 / 100 + 4 / 1000 = (100 + 20 + 4) / 1000)
= 2: 1 / 98 = 0.010204081632653061224489795918... (A021102)
= 3: 1 / 998 = 0.001002004008016032064128256513... (A022002)
= 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 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)

= 1: 10 / 89 = 0.11235955056179775280898876404...
= 2: 100 / 9899 = 0.010102030508132134559046368320...
= 3: 1000 / 998999 = 0.0010010020030050080130210340550...
= 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)

= 1: 1 / 89 = 0.011235955056179775280898876404... (A021093)
= 2: 1 / 9899 = 0.00010102030508132134559046368320...
= 3: 1 / 998999 = 0.0000010010020030050080130210340550...
= 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)

= 1: 10 / 889 = 0.011248593925759280089988751406...
= 2: 100 / 989899 = 0.00010102040713244482517913443694...
= 3: 1000 / 998998999 = 0.0000010010020040070130240440811492...
= 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)

= 1: 1 / 889 = 0.0011248593925759280089988751406... (A021893)
= 2: 1 / 989899 = 0.0000010102040713244482517913443694...
= 3: 1 / 998998999 = 0.0000000010010020040070130240440811492...
= 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

  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, " Cambridge University Press (2003).

External links