Content Curator
Recurrence Relations is a mathematical expression used to find out a particular term in a series and its relation with other elements of the series. In a series or sequence, the next term is decided by a fixed logic on which all the values of the equation are based. The recurrence relation, if derived, makes the work of finding the next value easy by simply substituting the values in the relation. Recurrence relations are extensively used in determining values in Arithmetical and Geometrical Progression as well.
Read More: Math Formulas
| Table of Content |
Key Takeaways: Recurrence Relation Formula, Recursive Relation, Sequence and Series, Fibonacci Series.
Recurrence Relation Formula
[Click Here for Sample Questions]
Recurrence Relation Formula is an expression to find the nth term of a series or sequence. The formula may also be used to represent the sequence and any desired term of the series can be found out by putting the values of the previous term of the series. For example, if you want to find out the 3rd term in a series then you need to have the value of the 2nd term.
The Recurrence Relation Formula to find out the nth term of the series is:
xn + 1 = f(xn); n>0
where f(xn) is the function which will be given.
We can also modify the Recurrence Formula to include the previous terms of the series as well. In that situation, the formula will be:
xn = f(n, xn-1); n>0
The find the Recurrence Relation of order k, the formula can be expressed as,
n = f(n, xn-1 , xn-2 , ……, xn-k) ; n-k>0
Read More:
Uses of Recurrence Relation
[Click Here for Sample Questions]
Recurrence Relation, where the value of the next term is dependent on the previous term in a sequence, is used to explain several other concepts of mathematics.
Fibonacci Series
The Fibonacci Series is a series or sequence in which every number of the series is the sum of the previous two terms. But the initial two terms in the fibonacci series are fixed. For example, 0,1,1,2,3,5,8,13,21,34,55………
In mathematical terms as per the Recurrence Relation Fibonacci series can be represented as:
Fn = Fn-1 + Fn-2
If we take the example of the above series 0,1,1,2,3,5,8,13,21,34,55 the first two initial terms are 0 and 1.
So, F0 = 0 and F1 = 1
Using the formula we can find any term of the series. For example, if we have to find F3 then:
F3 = F2 + F1 , from the series F2 = 1
F3 = 1 + 1 = 2
Factorial Equation
In finding the factorial of a number we use the Recurrence Relation Formula. Factorial of a number is the product of all numbers less than or equal to that number.
For example, 4! = 4*3*2*1 = 24.
The factorial of a number can be found with the Recurrence Relation Formula:
n ! = n(n-1)! ; n>0
When the value of n is 0
n ! = 0, which is the initial condition (F0)
Read More:
How To Solve Recurrence Relation Problems?
[Click Here for Sample Questions]
- Find the initial terms of the sequence or the series.
- With the help of the initial term, find the whole sequence.
- Find the logic of the sequence or the difference between two terms that also form a separate sequence.
- Add the second terms of the second sequence and equate it with the Recurrence Relation to find and solve it.
Things To Remember
[Click Here for Sample Questions]
- Recurrence Relation Formula is only applicable in the series and sequences or where there is a fixed logic in the difference of two terms.
- Recurrence Relation formula works for both arithmetic and geometric progression or series.
- In each application of the Recurrence Formula such as in the Fibonacci Series or Factorial a sequence or series follows which allows the use of Recurrence Formula possible.
Read More:
Sample Questions
Ques. Find the recurrence relation for the following series/sequence 1,6,9,18,21,34,60. (2 Marks)
Ans. The first step to solve a recurrence relation problem is to find whether the given numbers are in a series or not. For that, we need to check the difference between each term and decipher a fixed logic.
If we find the difference between each term there is no series or a fixed logic.
Difference between 1 and 6 is 5
Difference between 6 and 9 is 3
Difference between 9 and 18 is 9 and so on.
The difference between the terms are 5,3,9,3,13,26.
Hence, without a fixed logic of difference 1,6,9,18,21,34,60 is not a series/sequence. Therefore, Recurrence Relation is not applicable here.
Ques. What is the factorial of 10? (2 Marks)
Ans. As we know, the formula for finding the factorial of a number as per the recurrence relation is n! = n(n-1)!
Hence,
⇒ 10! = 10(10-1)!
⇒ 10 * 9!
⇒ 10*9*8*7*6*5*4*3*2*1 = 3628800
Therefore, the factorial of 10 is 3628800.
Ques. Solve the recurrence relation an = 3an-1 + 2 with the initial term 1. (3 Marks)
Ans. The initial term is given 1, i.e., a0 = 1. At first we need to find the sequence/series by putting different values of n in the recurrence relation.
The initial term is given therefore when n = 1
a1 = 3a0 + 2
a2 = 3a1 + 2 = 3(3a0 + 2) + 2
an = 3an-1 + 2 = 3(3(3(3…..(3a0 + 2) + 2) +2) ….+2) + 2
an = 3na0 + 2 . 3n-1 + 2 . 3n-2 +... + 2.3 + 2
Putting the value of a0 we get 3n + 2 . 3n-1 + 2 . 3n-2 +... + 2.3 + 2. Here, each term has 2 and an increasing order of 2. Hence, after simplifying we get,
2 + 2.3 + 2.32 + 2.33 + 2.34 + 2.3n-1.
Adding this we get (2 - 2.3n)/-2 which after solving comes to 3n - 1.
Adding the first 3n term to 3n - 1 we get 2 . 3n-1.
Therefore, the solution of the recurrence relation an = 3an-1 + 2 is an = 2 . 3n-1.
Ques. A series is given as 2,5,8,11,14,17,20,23,26. Find the recurrence relation and the initial term of the series/sequence. (2 Marks)
Ans. Let’s find the difference between each term.
5 - 2 = 3
8 - 5 = 3
11 - 8 = 3
26 - 23 = 3
So, we find the common difference between the terms is 3, hence it is a series and recurrence relation can be derived.
So, the recurrence relation is an = an-1.+ 3 and the initial term or a0 = 2.
Ques. The recurrence relation an = 2an-1 - 1 with initial term or a1 = 3. The solution of the relation is an = 2n + 1. Check whether the given solution is true or not. (2 Marks)
Ans. If an = 2n + 1 is the solution of the recurrence relation then a1 = 3 should satisfy it.
Let’s check, putting n = 1 in an = 2n + 1
a1 = 21 + 1 = 2 + 1 = 3
Thus, a1 = 3 is satisfying.
Now, the solution should fully satisfy the recurrence relation when put into it.
Putting an = 2n + 1 in an = 2an-1 - 1 we get,
2an-1 - 1 = 2(2n-1 + 1) - 1
2an-1 - 1 = 2n + 1
2an-1 - 1 = an
Thus, 2an-1 - 1 = an . Hence the solution an = 2n + 1 is correct.
Ques. Solve the recurrence relation an = an-1 + 2n. The initial term is given as a0 = 5. (3 Marks)
Ans. With the initial term let’s find the few terms of the series.
a1 = a0 + 2
a2 = a1 + 22 = (a0 + 2) + 22
a3 = a2 + 23 = ((a0 + 2) + 22) + 23
an = an-1 + 2n
a1 - a0 = 2
a2 - a1 = 22
a3 - a2 = 23
an - an-1 = 2n
Adding both sides we get,
an - a0 = 2n+1 + 2
Putting the value of a0 = 5 in the above equation we get
an - 5 = 2n+1 + 2
an = 2n+1 + 7
Thus, the solution of the recurrence relation is an = 2n+1 + 7.
Ques. Check whether 4? is the solution of the recurrence relation an = 3an-1 + 4an-2. (2 Marks)
Ans. If we think that 4n is the solution then we claim that an = 4n. To prove this we will put the value of an = 4n in the recurrence relation an = 3an-1 + 4an-2.
4n = 3(4n-1) + 4(4n-2)
= 3(4n-1) + 4n-2+1
= 3(4n-1) + 4n-1
= 4n-1(3 + 1)
= 4n-1(4)
= 4n-1+1 = 4n.
Thus, proved, 4? is the solution of the recurrence relation an = 3an-1 + 4an-2.
Ques. If the recurrence relation is an = 5an-1 - 6an-2 and the initial terms given are a0 = 1 and a1 = 3. What will be the sequence? (2 Marks)
Ans. Putting the different values of n in the recurrence relation we get,
When n = 2
a2 = 5a1 - 6a0 = 5*3 - 6*1 = 15 - 6 = 9
a2 = 9
When n = 3
a3 = 5a2 - 6a1 = 5*9 - 6*3 = 45 - 18 = 27
a3 = 27
When n = 4
a4 = 5a3 - 6a2 = 5*27 - 6*9 = 135 - 54 = 81
Therefore, the sequence is 1,3,9,27,81,243,729…
Read More:
Comments