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. This is also applicable for arithmetic and geometric sequence.
Recurrence Relation Definition
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.
Also, read:
Recurrence Relation Formula
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 numbers or 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.
Solving Recurrence Relations
To solve given recurrence relations we need to find the initial term first. Suppose we have been given a sequence;
an = 2an-1 – 3an-2
- Now the first step will be to check if initial conditions a0 = 1, a1 = 2, gives a closed pattern for this sequence.
- Then try with other initial conditions and find the closed formula for it.
- The result so obtained after trying different initial condition produces a series.
- Check the difference between each term, it will also form a sequence.
- We need to add all the terms of the new sequence, to understand which sequence is formed
- After understanding the pattern we can now identify the initial condition of the recurrence relation.
Recurrence Relation Problem
Now let us solve a problem based on the solution provided above.
Question: Solve the recurrence relation an = an-1 – n with the initial term a0 = 4.
Solution: Let us write the sequence based on the equation given starting with the initial number.
The sequence will be 4,5,7,10,14,19,…..
Now see the difference between each term.
a1 – a0 = 1
a2 – a1 = 2
a3 – a2 = 3
………
an – an-1 = n
and so on.
Now adding all these equations both at the right-hand side, we get;
1 +2+3+4+…..n = 1/2 [n(n+1)]
Whereas on the left-hand side we get;
(a1 – a0 ) + (a2 – a1 )+ (a3 – a2 )+ …….+ (an-1 – an-2 )+ (an – an-1 )
So you can see, all the terms get cancelled but – a0 and an
Therefore, an – a0 = 1/2 [n(n+1)]
or
an = 1/2 [n(n+1)] + a0
Hence, the solution to the recurrence relation with initial condition a0 = 4, is;
an = 1/2 [n(n+1)] + 4
Download BYJU’S-The Learning App and get personalised videos to understand the concepts in a better way.
