Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

community creator

What are recurrence relations?

Abdul sameer

A recurrence relation for the ana_{n} sequence in terms of one or more of its previous terms (a0a_{0},a1a_{1},a2a_{2}an1a_{n-1}) such that n>nin_{i}, where nin_{i} is a non-negative integer.

Example: Fibonacci series

{FnF_{n}} = 1, 1, 2, 3, 5,…

F0F_{0} = 1, F1F_{1} = 1, F2F_{2} = 2, F3F_{3} = 3, …

FnF_{n} = Fn1F_{n-1} + Fn2F_{n-2}, n >= 2

Degree of recurrence relation

The degree of recurrence relation is ‘K’ if the highest term of the numeric function is expressed in terms of its previous K terms.

Degree = highest coefficient - lowest coefficient

Linear recurrence relation with constant coefficients

The standard form of a linear recurrence relation with a constant coefficient is,

c0c_{0}ana_{n} + c1c_{1}an1a_{n-1} + c2c_{2}an2a_{n-2} +…+ ckc_{k}anka_{n-k}

Each term of the sequence {ana_{n}} is linear, the coefficients are c0c_{0}, c1c_{1}, c2c_{2},…,ckc_{k}

ana_{n} = a0a_{0}an1a_{n-1} + a1a_{1}an2a_{n-2}+…+an1a_{n-1}a0a_{0}

Homogeneous recurrence relation

The above equation is said to be homogenous if f( r ) = 0, i.e,

c0c_{0}ana_{n} + c1c_{1}an1a_{n-1} +…+ckc_{k}anka_{n-k} = 0

Non-homogeneous recurrence relation

Equation is non-homogeneous if f( r ) != 0

c0c_{0}ana_{n} + c1c_{1}an1a_{n-1} +…+ ckc_{k}anka_{n-k} != 0

General solution of the Fibonacci relation

If FnF_{n} satisfies the fibonacci relation ana_{n} = Fn1F_{n-1} + Fn2F_{n-2} for n>=2, then there are constants c1c_{1} and c2c_{2} such that,

FnF_{n} = c1c_{1}( 1+2.23602\frac{1 + 2.2360}{2} )^n + c1c_{1}( 12.23602\frac{1 - 2.2360}{2} )^n

Let the constant be completely determined by the initial conditions.

Solving recurrence relations by the method of characteristic roots

Let the homogeneous linear recurrence relation with constant coefficient be,

ana_{n} = c1c_{1}an1a_{n-1} + c2c_{2}an2a_{n-2} +…+ ckc_{k}anka_{n-k}

Assume that there exists a solution of form ana_{n} = rnr^{n} and substitute in the above relation.

rkr^{k} - c1c_{1}rk1r^{k-1} - c2c_{2}rk2r^{k-2} -…-ckc_{k} = 0 – characteristic equation.

r1r_{1}, r2r_{2}, r3r_{3},…,rkr_{k} are called characteristic roots.

  • Roots are real and unequal: If the roots r1r_{1}, r2r_{2},…,rkr_{k} are real and unequal then the homogeneous solution is,

ana_{n} = c1c_{1}r1r_{1}^n + c2c_{2}r2r_{2}^n +…+ ckc_{k}rkr_{k}^n

c1c_{1}, c2c_{2} are constants that are determined by the given initial conditions.

  • Roots are real and equal: If two roots r1r_{1}, r2r_{2} are equal ( r1r_{1} = r2r_{2} ), then the homogeneous solution is,

ana_{n} = ( c1c_{1} + nc2c_{2} )rnr_{n}


community creator

View all Courses

Keep Exploring