This site is supported by donations to The OEIS Foundation.

# Recurrence

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
 lim n → ∞  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.

## Recurrences with constant coefficients

### Linear recurrences with constant coefficients

Main article page: Linear recurrence relations 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) ${\displaystyle k}$, is a recurrence of the form

${\displaystyle a_{n}:=c_{1}\,a_{n-1}+c_{2}\,a_{n-2}+\cdots +c_{k}\,a_{n-k},\quad c_{k}\neq 0,\,n\geq k,}$

with initial conditions

${\displaystyle a_{n}:=C_{n},\,0\leq n\leq k-1,}$

where

${\displaystyle \{C_{0},\,\ldots ,\,C_{k-1}\}}$

is called the signature.

Equivalently, it may also be expressed as an equation of the form

${\displaystyle \sum _{i=0}^{k}c_{i}\,a(n-i)=c_{0}\,a(n)+c_{1}\,a(n-1)+c_{2}\,a(n-2)+\cdots +c_{k}\,a(n-k)=0.\,}$
##### Homogeneous linear recurrences (of order 1) with constant coefficients
###### Powers of 1
${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=1\,a_{n-1},\quad n\geq 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)

${\displaystyle G_{\{1^{n},\,n\geq 0\}}(x)={\frac {1}{1-x}}={\frac {(x^{-1})^{1}}{(x^{-1})^{1}-(x^{-1})^{0}}},}$
and setting
 x  − 1
to
 10 k
, we get the form
${\displaystyle {\frac {(10^{k})^{1}}{(10^{k})^{1}-(10^{k})^{0}}}={\frac {10^{k}}{10^{k}-1}}=\sum _{n=0}^{\infty }{\frac {1}{(10^{k})^{n}}},\quad k\geq 1.\,}$
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

${\displaystyle \sum _{n=0}^{\infty }{\frac {1}{(10^{k})^{n+1}}},\quad k\geq 1.}$
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
${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=2\,a_{n-1},\quad n\geq 1.}$
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)

${\displaystyle G_{\{2^{n},\,n\geq 0\}}(x)={\frac {1}{1-2x}}={\frac {(x^{-1})^{1}}{(x^{-1})^{1}-2\,(x^{-1})^{0}}},}$
and setting
 x  − 1
to
 10 k
, we get the form
${\displaystyle {\frac {(10^{k})^{1}}{(10^{k})^{1}-2\,(10^{k})^{0}}}={\frac {10^{k}}{10^{k}-2}}=\sum _{n=0}^{\infty }{\frac {2^{n}}{(10^{k})^{n}}},\quad k\geq 1.\,}$
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
 2 n (10 k) 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

${\displaystyle {\frac {1}{(10^{k})^{1}-2\,(10^{k})^{0}}}={\frac {1}{10^{k}-2}}=\sum _{n=0}^{\infty }{\frac {2^{n}}{(10^{k})^{n+1}}},\quad k\geq 1.\,}$
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
 2 n (10 k) 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

${\displaystyle F_{0}:=0;\ F_{1}:=1;}$
${\displaystyle F_{n}:=F_{n-1}+F_{n-2},\quad n\geq 2.}$
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

${\displaystyle G_{\{F_{n},\,n\geq 0\}}(x)={\frac {x}{1-x-x^{2}}}=\sum _{n=0}^{\infty }F_{n}\,x^{n}.}$

Rewriting the generating function as (which shows the form of the recurrence in the denominator)

${\displaystyle G_{\{F_{n},\,n\geq 0\}}(x)={\frac {(x^{-1})^{1}}{(x^{-1})^{2}-(x^{-1})^{1}-(x^{-1})^{0}}},}$
and setting
 x  − 1
to
 10 k
, we get the form
${\displaystyle {\frac {(10^{k})^{1}}{(10^{k})^{2}-(10^{k})^{1}-(10^{k})^{0}}}={\frac {10^{k}}{10^{2k}-10^{k}-1}}=\sum _{n=0}^{\infty }{\frac {F_{n}}{(10^{k})^{n}}},\quad k\geq 1.}$
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

${\displaystyle {\frac {1}{(10^{k})^{2}-(10^{k})^{1}-(10^{k})^{0}}}={\frac {1}{10^{2k}-10^{k}-1}}=\sum _{n=0}^{\infty }{\frac {F_{n}}{(10^{k})^{n+1}}},\quad k\geq 1.\,}$
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

${\displaystyle a_{0}:=0;\ a_{1}:=0;\ a_{2}:=1;}$
${\displaystyle a_{n}:=a_{n-1}+a_{n-2}+a_{n-3},\quad n\geq 3.}$
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

${\displaystyle G_{\{a_{n},\,n\geq 0\}}(x)={\frac {x^{2}}{1-x-x^{2}-x^{3}}}=\sum _{n=0}^{\infty }a_{n}\,x^{n}.}$

Rewriting the generating function as (which shows the form of the recurrence in the denominator)

${\displaystyle G_{\{a_{n},\,n\geq 0\}}(x)={\frac {(x^{-1})^{1}}{(x^{-1})^{3}-(x^{-1})^{2}-(x^{-1})^{1}-(x^{-1})^{0}}},}$
and setting
 x  − 1
to
 10 k
, we get the form
${\displaystyle {\frac {(10^{k})^{1}}{(10^{k})^{3}-(10^{k})^{2}-(10^{k})^{1}-(10^{k})^{0}}}={\frac {10^{k}}{10^{3k}-10^{2k}-10^{k}-1}}=\sum _{n=0}^{\infty }{\frac {a_{n}}{(10^{k})^{n}}},\quad k\geq 1.\,}$
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

${\displaystyle {\frac {1}{(10^{k})^{3}-(10^{k})^{2}-(10^{k})^{1}-(10^{k})^{0}}}={\frac {1}{10^{3k}-10^{2k}-10^{k}-1}}=\sum _{n=0}^{\infty }{\frac {a_{n}}{(10^{k})^{n+1}}},\quad k\geq 1.\,}$
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
${\displaystyle a_{n}:=c_{1}\,a_{n-1}+c_{2}\,a_{n-2}+\cdots +c_{k}\,a_{n-k}+f(n),\quad c_{k}\neq 0,\,n\geq k,}$

with initial conditions

${\displaystyle a_{i}:=C_{i},\,0\leq i\leq k-1,}$

where

${\displaystyle \{C_{0},\,\ldots ,\,C_{k-1}\}}$
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

${\displaystyle \left(\sum _{i=0}^{k}c_{i}\,a(n-i)\right)+f(n)={\Bigg (}c_{0}\,a(n)+c_{1}\,a(n-1)+c_{2}\,a(n-2)+\cdots +c_{k}\,a(n-k){\Bigg )}+f(n)=0,\,}$
##### Non-homogeneous linear recurrences (of order 1) with constant coefficients

Examples:

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=2\,a_{n-1}+1,\quad n\geq 1.}$

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=2\,a_{n-1}+n,\quad n\geq 1.}$

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=2\,a_{n-1}+2^{n},\quad n\geq 1.}$
##### Non-homogeneous linear recurrences (of order 2) with constant coefficients

Examples:

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=3\,a_{n-1}+2\,a_{n-2}+n,\quad n\geq 1.}$

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

${\displaystyle \sum _{i=0}^{\lfloor k/2\rfloor }d_{i}\,a(n-i)\,a(n-k+i)=0,\,}$
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

${\displaystyle \sum _{i=0}^{\lfloor k/2\rfloor }d_{i}\,a(n-i)\,a(n-k+i)+\left(\sum _{i=0}^{k}c_{i}\,a(n-i)\right)+f(n)=0,\,}$
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:

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=2\,{a_{n-1}}^{2},\quad n\geq 1.}$
##### Homogeneous quadratic recurrences (of order 2) with constant coefficients

Examples:

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=3\,{a_{n-1}}^{2}+2\,{a_{n-2}}^{2},\quad n\geq 1.}$

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

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=2\,{a_{n-1}}^{2}+1,\quad n\geq 1.}$

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=2\,{a_{n-1}}^{2}+n,\quad n\geq 1.}$

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=2\,{a_{n-1}}^{2}+2^{n},\quad n\geq 1.}$
##### Non-homogeneous quadratic recurrences (of order 2) with constant coefficients

Examples:

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=3\,{a_{n-1}}^{2}+2\,{a_{n-2}}^{2}+n,\quad n\geq 1.}$

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

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=2\,{a_{n-1}}^{3},\quad n\geq 1.}$
##### Homogeneous cubic recurrences (of order 2) with constant coefficients

Examples:

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=3\,{a_{n-1}}^{3}+2\,{a_{n-2}}^{2},\quad n\geq 1.}$

#### Non-homogeneous cubic recurrences with constant coefficients

##### Non-homogeneous cubic recurrences (of order 1) with constant coefficients

Examples:

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=2\,{a_{n-1}}^{3}+1,\quad n\geq 1.}$

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=2\,{a_{n-1}}^{3}+n,\quad n\geq 1.}$

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=2\,{a_{n-1}}^{3}+2^{n},\quad n\geq 1.}$
##### Non-homogeneous cubic recurrences (of order 2) with constant coefficients

Examples:

${\displaystyle a_{0}:=1;}$
${\displaystyle a_{n}:=3\,{a_{n-1}}^{3}+2\,{a_{n-2}}^{2}+n,\quad n\geq 1.}$

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