The recurrence relation is a procedure that helps you find missing terms in a sequence. The process of solving is done recursively.
The number of terms arranged in a particular way is called a sequence. A recurrence relation occurs when some number in a sequence depends on the previous numbers
Example: 1,2,3,4… is a sequence of numbers whose difference is 1. By seeing this sequence you can say that the next number will be 5.
Common Examples of sequence are Arithmetic progression, Geometric Progression, and Fibonacci series.
Recurrence Relation Sequence:
What is a sequence?
The sequence is a set of terms where there’s a common role governing how we get from one term to the next term.
Say, for example, you have a sequence of numbers 6,13,27,55,… and we have to find the next number
So for instance, if we have six and double it, we’re going to have 12, and then having one gives 13. Likewise, if I’ve got 13 and double it, which will be 26 and have one. I get 27 and doubling 27 is 54 and adding one is 55. So you can see how we can build up the sequence. Now many authors use a particular type of notation for terms in sequences and the common notation tends to be a U. The next number that will come up in a sequence is double 55 and add 1 which is 2 * 55 + 1 = 111
what are we doing to any term to get the next term in the sequence? Well, we’re doubling it. So that would be twice U n. We’re adding one to that answer. This gives us the next term in the sequence. And the next term in the sequence would be you with a subscript N plus one… And this particular type of equation is called a recurrence relation.
If you have to find the 10th or 100th term, this is where things might get complex and so arises the need to set a formula to find it. To set the formula for it, identify what type of sequence it is and move ahead. You can find more details in arithmetic progression and geometric progression
Example With Problem:
Examples are shown in the video below
4 Methods To Solve Recurrence Relation:
- Substitution Method: The substitution method is the algebraic method to solve simultaneous linear equations. As the word says, in this method, the value of one variable from one equation is substituted in the other equation. Here we substitute the initial or given value in sequence to find the nth term. There are two ways to solve the substitution method
- Forward Substitution Method: Using the below 4 steps we can find recurrence relation using this method. 1) Take the recurrence relation and initial condition 2)Put initial condition in equation and look for the pattern 3) Guess the pattern 4)Prove the pattern is correct. Example: We can calculate the running time for n=0,1,2,.. as follows n T(n) 1 1 2 T(2-1) + 1 = 1 + 1 = 2 3 T(3-1) + 1 = 2 + 1 = 3 Verifying the pattern here, T(n) = n
- Backward Substitution Method: In the forward substitution method, we put n=0,1,2… in the recurrence relation until we see a pattern. In backward substitution, we do the opposite i.e. we put n=n,n−1,n−2 until we see the pattern. After we see the pattern, we make guesswork for the running time and we verify the guesswork
- Iteration Method recurrence: The iteration method is a method of solving a recurrence relation. The general idea is to iteratively substitute the value of the recurrent part of the equation until a pattern (usually a summation) is noticed, at which point the summation can be used to evaluate the recurrence.
- Example: T(n) = 2T(n/2) + n , T(1) = 1. Expand and solve this recurrence relation. So what exactly are we doing here? We are going to find the pattern and reduce the given example till we reach the value of n as 1 1) Put n as n/2 so the given equation becomes T(n/2) = 2T((n/2)/2) + n/2 T(n/2) = 2T(n/2^2) + n/2 2)Substitute the value of T(n/2) in original equation T(n) = 2[2T(n/2^2) + n/2] + n T(n) = 2^2T(n/2^2) + n + n T(n) = 2^2T(n/2^2) + 2n 3) To find the pattern repeat step 2 by substituting n with n/2^2 we get, T(n/2^2) = 2T(n/2^3) + n/2^2 Substituting the value of t(n/2^2) in original equation from step 1 we get, T(n) = 2^3 T(n/2^3) + 3n 4) For ith term it will become, T(n) = 2^i T(n/2^i) + in But then we need to have value of i, for that lets compare n/2^i = 1 therefore n = 2^i Taking log on both sides, i=log n to base 2 5) Putting the value of i in equation derived in step 4 T(n) = nT(n/n) + (log n) n….. here 2^i = n from step 4 T(n) = nT(1) + n(log n) T(n) = n + nlogn So the time complexity here is O(n log n)
- Recursion Tree Method: In this method, a recurrence relation is converted into recursive trees. Each node represents the cost incurred at various levels of recursion. To find the total cost, the costs of all levels are summed up.
- Master Method: The master method is a formula for solving recurrence relations of the form: T(n) = aT(n/b) + f(n), where, n = size of input a = number of subproblems in the recursion n/b = size of each subproblem. All subproblems are assumed to have the same size.
How do you identify a recurrence relation?
Identify if the sequence is finite or infinite.
If the series is infinite then check the relation between numbers.
Based on the relation between numbers in sequence develop the formula.
Different Types of Recurrence relation
- Linear
- Non Linear
- Homogenous Recurrence Relation
- Non Homogenous Recurrence Relation
- First Order
- Higher Order
- Divide and conquer: – general and binary
Linear Recurrence Relation:
Linear recurrences are particular cases of sequences of numbers that, given initial values, the other elements can always be calculated as linear combinations of the previous
Areas of Application:
Number Theory:
- Fibonacci Sequence
- Harmonic Numbers
- Partition of Integer
- Pell Numbers
- Pells Equation
- Diophantine Equation
- Modular forms
Combinatorics:
- Binomial Coefficient
- Pascal’s Triangle
- Dereangements
- Distribution of Identical Objects into Identical Bins
- Distribution of Distinct Objects into Identical Bins
- Permutations
- Combinations
- Partitions
- Catalian Numbers
- Markov Chains
Calculus:
- Arithmetic Progression
- Geometric Progression
- Euler’s Method
- Differential Equations
Computer Science:
- Recursive Backtracking
- Dynamic Programming
- Memoization
- Computer Graphics
- Cryptography
- Numerical Analysis
- Huffman Coding
- Machine Learning
- Algorithmic Design
