Recurrence

This article needs more work.

Please help by expanding it!

A recurrence relation (also called recursive relation, difference equation or recursive definition) 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

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

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) $k$, is a recurrence of the form

$a_n:=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k},c_k\ne 0,n\ge k,$

with initial conditions

$a_n:=C_n,0\le n\le k-1,$

where

$\{C_0,\dots ,C_{k-1}\}$

is called the signature.

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

$\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

$a_0:=1;$

$a_n:=1a_{n-1},n\ge 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)

$G_{\{1^n,n\ge 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

$\frac{(10^k{)}^1}{(10^k{)}^1-(10^k{)}^0}=\frac{10^k}{10^k-1}=\sum _{n=0}^{\mathrm{\infty }}\frac{1}{(10^k{)}^n},k\ge 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

$\sum _{n=0}^{\mathrm{\infty }}\frac{1}{(10^k{)}^{n+1}},k\ge 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

$a_0:=1;$

$a_n:=2a_{n-1},n\ge 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)

$G_{\{2^n,n\ge 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

$\frac{(10^k{)}^1}{(10^k{)}^1-2(10^k{)}^0}=\frac{10^k}{10^k-2}=\sum _{n=0}^{\mathrm{\infty }}\frac{2^n}{(10^k{)}^n},k\ge 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

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

$F_0:=0;F_1:=1;$

$F_n:=F_{n-1}+F_{n-2},n\ge 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

$G_{\{F_n,n\ge 0\}}(x)=\frac{x}{1-x-x^2}=\sum _{n=0}^{\mathrm{\infty }}{F}_n{x}^n.$

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

$G_{\{F_n,n\ge 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

$\frac{(10^k{)}^1}{(10^k{)}^2-(10^k{)}^1-(10^k{)}^0}=\frac{10^k}{10^{2k}-10^k-1}=\sum _{n=0}^{\mathrm{\infty }}\frac{F_n}{(10^k{)}^n},k\ge 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

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

$a_0:=0;a_1:=0;a_2:=1;$

$a_n:=a_{n-1}+a_{n-2}+a_{n-3},n\ge 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

$G_{\{a_n,n\ge 0\}}(x)=\frac{x^2}{1-x-x^2-x^3}=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n.$

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

$G_{\{a_n,n\ge 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

$\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}^{\mathrm{\infty }}\frac{a_n}{(10^k{)}^n},k\ge 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

$\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}^{\mathrm{\infty }}\frac{a_n}{(10^k{)}^{n+1}},k\ge 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

$a_n:=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}+f(n),c_k\ne 0,n\ge k,$

with initial conditions

$a_i:=C_i,0\le i\le k-1,$

where

$\{C_0,\dots ,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

$(\sum _{i=0}^k{c}_{i}a(n-i))+f(n)=(c_{0}a(n)+c_{1}a(n-1)+c_{2}a(n-2)+\cdots +c_{k}a(n-k))+f(n)=0,$

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

Examples:

$a_0:=1;$

$a_n:=2a_{n-1}+1,n\ge 1.$

$a_0:=1;$

$a_n:=2a_{n-1}+n,n\ge 1.$

$a_0:=1;$

$a_n:=2a_{n-1}+2^n,n\ge 1.$

Non-homogeneous linear recurrences (of order 2) with constant coefficients

Examples:

$a_0:=1;$

$a_n:=3a_{n-1}+2a_{n-2}+n,n\ge 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

$\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

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

$a_0:=1;$

$a_n:=2{a_{n-1}}^2,n\ge 1.$

Homogeneous quadratic recurrences (of order 2) with constant coefficients

Examples:

$a_0:=1;$

$a_n:=3{a_{n-1}}^2+2{a_{n-2}}^2,n\ge 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:

$a_0:=1;$

$a_n:=2{a_{n-1}}^2+1,n\ge 1.$

$a_0:=1;$

$a_n:=2{a_{n-1}}^2+n,n\ge 1.$

$a_0:=1;$

$a_n:=2{a_{n-1}}^2+2^n,n\ge 1.$

Non-homogeneous quadratic recurrences (of order 2) with constant coefficients

Examples:

$a_0:=1;$

$a_n:=3{a_{n-1}}^2+2{a_{n-2}}^2+n,n\ge 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:

$a_0:=1;$

$a_n:=2{a_{n-1}}^3,n\ge 1.$

Homogeneous cubic recurrences (of order 2) with constant coefficients

Examples:

$a_0:=1;$

$a_n:=3{a_{n-1}}^3+2{a_{n-2}}^2,n\ge 1.$

Non-homogeneous cubic recurrences with constant coefficients

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

Examples:

$a_0:=1;$

$a_n:=2{a_{n-1}}^3+1,n\ge 1.$

$a_0:=1;$

$a_n:=2{a_{n-1}}^3+n,n\ge 1.$

$a_0:=1;$

$a_n:=2{a_{n-1}}^3+2^n,n\ge 1.$

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

Examples:

$a_0:=1;$

$a_n:=3{a_{n-1}}^3+2{a_{n-2}}^2+n,n\ge 1.$

See also

• Homogeneous recurrence
• Non-homogeneous recurrence

• n th-order recurrence

External links

• Shafiei, Niloufar. “Solving Linear Recurrence Relations”. http://www.cse.yorku.ca/course_archive/2008-09/S/1019/Website_files/21-linear-recurrences.pdf. 
• Fischer, Georg; Mathar, Richard (2020). “P-finite recurrences from sqrt generating functions”. https://www.mpia.de/~mathar/public/fischer20200119.pdf. 
• Mathar, Richard (2014). “Some linear recurrences with constant coefficients”. http://www.mpia.de/~mathar/public/mathar20071126.pdf. 
• Recurrence relation—Wikipedia.org.