This site is supported by donations to The OEIS Foundation.

# Recurrence

(Redirected from Recurrence relation)

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

## 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.}$