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: ${\displaystyle \scriptstyle F_{n}\,=\,F_{n-1}+F_{n-2},\,n\,\geq \,2,\,}$ with ${\displaystyle \scriptstyle F_{0}\,=\,0,\,F_{1}\,=\,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 ${\displaystyle \scriptstyle a_{n}\,=\,n\times (n+1)\,=\,n^{2}+n,\,n\,\geq \,0;\,}$ but since we have ${\displaystyle \scriptstyle a_{n-1}\,=\,(n-1)\times n\,=\,n^{2}-n,\,n\,\geq \,1,\,}$ we can trivially obtain the recursive definition ${\displaystyle \scriptstyle a_{n}\,=\,a_{n-1}+(a_{n}-a_{n-1})\,=\,a_{n-1}+2n,\,n\,\geq \,1,\,}$ (hence difference equation) with ${\displaystyle \scriptstyle a_{0}\,=\,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 ${\displaystyle \scriptstyle x_{n}\,=\,{\frac {x_{n-1}}{2}}+{\frac {1}{x_{n-1}}},\,n\,\geq \,1,\,}$ with ${\displaystyle \scriptstyle x_{0}\,=\,1\,}$; this has the limit ${\displaystyle \scriptstyle \lim _{n\to \infty }x_{n}\,=\,{\sqrt {2}}\,}$.[4] (See A001601 for the numerators and A051009 for the denominators of ${\displaystyle \scriptstyle x_{n}\,}$.)

## 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 ${\displaystyle x^{-1}}$ to ${\displaystyle 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 ${\displaystyle k}$, we have (note that overlapping would occur if powers of 1 had more than ${\displaystyle k}$ digits)

${\displaystyle k}$ = 1: 10 / 9 = 1.11111111111111111111111111111...
${\displaystyle k}$ = 2: 100 / 99 = 1.0101010101010101010101010101...
${\displaystyle k}$ = 3: 1000 / 999 = 1.001001001001001001001001001...
${\displaystyle 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 ${\displaystyle k}$, we have (note that overlapping would occur if powers of 1 had more than ${\displaystyle k}$ digits)

${\displaystyle k}$ = 1: 1 / 9 = 0.111111111111111111111111111111... (A000012)
${\displaystyle k}$ = 2: 1 / 99 = 0.010101010101010101010101010101... (A000035)
${\displaystyle k}$ = 3: 1 / 999 = 0.001001001001001001001001001001...
${\displaystyle 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 ${\displaystyle x^{-1}}$ to ${\displaystyle 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 ${\displaystyle k}$, we have (note that overlapping would occur if powers of 1 had more than ${\displaystyle k}$ digits)

${\displaystyle k}$ = 1: 10 / 8 = 1.25 (here ${\displaystyle \scriptstyle \sum _{n=3}^{\infty }{\frac {2^{n}}{(10^{k})^{n}}}}$ = 0.01, and 1 + 2 / 10 + 4 / 100 = (100 + 20 + 4) / 100)
${\displaystyle k}$ = 2: 100 / 98 = 1.0204081632653061224489795918...
${\displaystyle k}$ = 3: 1000 / 998 = 1.002004008016032064128256513...
${\displaystyle 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 ${\displaystyle k}$, we have (note that overlapping occurs when powers of 2 have more than ${\displaystyle k}$ digits)

${\displaystyle k}$ = 1: 1 / 8 = 0.125 (here ${\displaystyle \scriptstyle \sum _{n=3}^{\infty }{\frac {2^{n}}{(10^{k})^{n+1}}}}$ = 0.001, and 1 / 10 + 2 / 100 + 4 / 1000 = (100 + 20 + 4) / 1000)
${\displaystyle k}$ = 2: 1 / 98 = 0.010204081632653061224489795918... (A021102)
${\displaystyle k}$ = 3: 1 / 998 = 0.001002004008016032064128256513... (A022002)
${\displaystyle 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 ${\displaystyle x^{-1}}$ to ${\displaystyle 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 ${\displaystyle k}$, we have (note that overlapping occurs when Fibonacci numbers have more than ${\displaystyle k}$ digits)

${\displaystyle k}$ = 1: 10 / 89 = 0.11235955056179775280898876404...
${\displaystyle k}$ = 2: 100 / 9899 = 0.010102030508132134559046368320...
${\displaystyle k}$ = 3: 1000 / 998999 = 0.0010010020030050080130210340550...
${\displaystyle 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 ${\displaystyle k}$, we have (note that overlapping occurs when Fibonacci numbers have more than ${\displaystyle k}$ digits)

${\displaystyle k}$ = 1: 1 / 89 = 0.011235955056179775280898876404... (A021093)
${\displaystyle k}$ = 2: 1 / 9899 = 0.00010102030508132134559046368320...
${\displaystyle k}$ = 3: 1 / 998999 = 0.0000010010020030050080130210340550...
${\displaystyle 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 ${\displaystyle x^{-1}}$ to ${\displaystyle 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 ${\displaystyle k}$, we have (note that overlapping occurs when tribonacci numbers have more than ${\displaystyle k}$ digits)

${\displaystyle k}$ = 1: 10 / 889 = 0.011248593925759280089988751406...
${\displaystyle k}$ = 2: 100 / 989899 = 0.00010102040713244482517913443694...
${\displaystyle k}$ = 3: 1000 / 998998999 = 0.0000010010020040070130240440811492...
${\displaystyle 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 ${\displaystyle k}$, we have (note that overlapping occurs when tribonacci numbers have more than ${\displaystyle k}$ digits)

${\displaystyle k}$ = 1: 1 / 889 = 0.0011248593925759280089988751406... (A021893)
${\displaystyle k}$ = 2: 1 / 989899 = 0.0000010102040713244482517913443694...
${\displaystyle k}$ = 3: 1 / 998998999 = 0.0000000010010020040070130240440811492...
${\displaystyle 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) ${\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}+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 ${\displaystyle 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 ${\displaystyle \scriptstyle 1+{\lfloor k/2\rfloor }\,}$ coefficients ${\displaystyle \scriptstyle d_{i}\,(\forall i)\,}$ are constants. (Note that there are no squared ${\displaystyle \scriptstyle a(j)\,(\forall 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 ${\displaystyle \scriptstyle \sum _{i=0}^{k}|c_{i}|\,\neq \,0\,}$ or ${\displaystyle \scriptstyle f(n)\,\neq \,0\,}$ and the ${\displaystyle \scriptstyle 1+{\lfloor k/2\rfloor }\,}$ coefficients ${\displaystyle \scriptstyle d_{i}\,(\forall i)\,}$ and ${\displaystyle \scriptstyle c_{i}\,(\forall i)\,}$ and are constants. (Note that there are no squared ${\displaystyle \scriptstyle a(j)\,(\forall 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.}$

4. Steven R. Finch, Mathematical Constants, Section 1.1, "Pythagoras' Constant, ${\displaystyle \scriptstyle {\sqrt {2}}}$" Cambridge University Press (2003).