INTRODUCTION TO RECURRENCE RELATION

INTRODUCTION TO RECURRENCE RELATION

DEFINITION: Recurrence relation is a procedure of representing the n'th term of the sequence as a function instead of it's previous terms.

consider  the following Fibonacci sequence :

here, 

         a₂ =  a₁  +  a₀

      a₃ = a₂ + a₁

      a₄ = a₃ + a_{2           is true for all values of n>=2 ; a0 = 0 and a1 = 1;}

                                                      _{(exit criteria / initial condition)}

_{consider a sequence {}a_0, a₁, a₂, a₃, a₄, a₅, a₆ }

A recurrence relation is an equation that represents the n'th term of the sequence is terms of one or more of its previous terms.

   The explicitly specified values of the terms of the sequence are known as the initial condition condition of the recurrence relation.

Example:

 a_n = a_n-1 + a_n-2           where n>= 2; a₀ = 0, a₁ = 1