 # Recurrence Relation

A recurrence relation is an equation which represents a sequence based on some rule. It helps in finding the subsequent term (next term) dependent upon the preceding term (previous term). If we know the previous term in a given series, then we can easily determine the next term. Since a standard pattern is developed now, we can find the set of new terms.

## Recurrence Relation Definition and Formula

When we speak about a standard pattern, all the terms in the relation or equation have the same characteristics. It means if there is a value of ‘n’, it can be used to determine the other values by just entering the value of ‘n’.

The value of n should be organised and accurate, which is known as the Simplest form. In case of the simplest form of any such relation, the next term is dependent only upon the previous term. The sequence or series generated by recurrence relation is called a Recurrence Sequence.

Let us assume xn is the nth term of the series. Then the recurrence relation is shown in the form of;

 xn + 1 = f(xn) ; n>0

Where f(xn) is the function.

We can also define a recurrence relation as an expression that represents each element of a series as a function of the preceding ones.

 xn= f(n,xn-1) ; n>0

To write the recurrence relation of first-order, say order k, the above formula can be represented as;

 xn = f(n, xn-1 , xn-2 , ……, xn-k) ; n-k>0

## Examples of Recurrence Relation

In Mathematics, we can see many examples of recurrence based on series and sequence pattern. Let us see some of the examples here.

### Factorial Representation

We can define the factorial by using the concept of recurrence relation, such as;

n!=n(n-1)! ; n>0

When n = 0,

0! = 1 is the initial condition.

To find the further values we have to expand the factorial notation, where the succeeding term is dependent on the preceding one.

### Fibonacci Numbers

In Fibonacci series, the succeeding terms are dependent on the last two preceding terms. Therefore, this series is the best example of recurrence. As we know from the definition of the Fibonacci sequence,

Fn = Fn-1 + Fn-2

Now, if we take the initial values;

F0 = 0 and F1 = 1

So, F2 = F1 + F0 = 0 + 1 = 1

In the same way, we can find the next succeeding terms, such as;

F3 = F2 + F1

F4 = F3 + F2

And so on.

Thus, the Fibonacci series is given by;

 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …∞

In the same way, there are other examples of recurrence such as a logical map, binomial coefficients where the same concept is applicable. Also, arithmetic and geometric series could be called a recurrence sequence.

Download BYJU’S-The Learning App and get personalised videos to understand the concepts in a better way.