This site is supported by donations to The OEIS Foundation.

# Recurrence

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

- 1 Recurrences with constant coefficients
- 1.1 Linear recurrences with constant coefficients
- 1.1.1 Homogeneous linear recurrences with constant coefficients
- 1.1.2 Non-homogeneous linear recurrences with constant coefficients

- 1.2 Quadratic recurrences with constant coefficients
- 1.3 Cubic recurrences with constant coefficients

- 1.1 Linear recurrences with constant coefficients
- 2 See also
- 3 Notes
- 4 External links

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

- ↑ "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

- Niloufar Shafiei, Solving Linear Recurrence Relations.