What is the Recurrence Relation?

In this Article, You will learn Recurrence Relation. In DSA which topic this cover

Simplified Recurrence Relation

An Equation that expresses an in terms of one or more in the previous term of any Sequence.

Means: For finding any nth term need to calculate from previous terms

Formula

Example: Fibonacci Series

1,1,2,3,5,8....nth

in this case the formula for calculating the Recurrence Relation of Fibonacci Series.

n = (n-1) + (n-2)
from two previous term we calculate the next term

Let's See One more example

A Sequence is : 3, 9, 27, 81......n
The formula for reccurence relation in this Sequence is :
N-term = 3 * a(n-1)
For finding the Relation.

where 
A5 = 3 * a(5-1)
A5 = 243

This DSA Topic you can't learn without Recurrence Relation

1. • Divide and conquer algorithms

     • Merge sort

     • Quicksort

     • Binary search

     • Heap sort

     • Fibonacci sequence and related problems

     • Tower of Hanoi

     • Graph traversal algorithms

     • - Depth-first search

     • - Breadth-first search

     • Matrix chain multiplication

     • Knapsack problem and related problems

Types of Recurrence Relation

1. Linear Recurrence Relations: In these relations, each term depends on a fixed number of previous terms, typically one or two. The general form of a linear recurrence relation of order k is:

a(n) = c1a(n-1) + c2a(n-2) + ... + ck*a(n-k)
where c1, c2, ..., ck are constants.

1. Homogeneous Recurrence Relations: These relations have a right-hand side of the equation equal to zero, meaning no external factors affect the recurrence. The general form of a homogeneous recurrence relation is:

a(n) = c1a(n-1) + c2a(n-2) + ... + ck*a(n-k)
where c1, c2, ..., ck are constants.

1. Non-homogeneous Recurrence Relations: These relations have a non-zero right-hand side of the equation, indicating external factors affecting the recurrence. The general form of a non-homogeneous recurrence relation is:

a(n) = c1a(n-1) + c2a(n-2) + ... + ck*a(n-k) + f(n)
where c1, c2, ..., ck are constants and f(n) is a non-zero function of n.

1. Master Theorem Recurrence Relations: These relations can be solved using the Master Theorem, a method for analyzing the time complexity of divide-and-conquer algorithms. The general form of a recurrence relation solvable with the Master Theorem is:ved using the Master Theorem is:

T(n) = a*T(n/b) + f(n)
where a ≥ 1, b > 1, and f(n) is a non-negative function.

Alright! If you Understand Till now please Comment below

Methods to Solve this Recurrence Relation📍

• Substitution

• Iteration

• Generating Functions

Substitution Method

Substitution: Begin by making an initial guess for the solution and verifying its correctness by substituting it into the relation. If incorrect, refine the guess and repeat the process.

Example :)

Suppose we have a recurrence relation T(n) = T(n-1) + n, with the initial condition T(1) = 1.

Make an initial guess: Let's guess that T(n) = (n * (n + 1)) / 2.

Substitute the guess into the relation to check if it holds:

T(n) = T(n-1) + n (n (n + 1)) / 2 = ((n - 1) n) / 2 + n

Check if the substitution is correct:
((n (n + 1)) / 2) - (((n - 1) n) / 2) = n ((n^2 + n) - (n^2 - n)) / 2 = n (2n) / 2 = n n = n

The substitution is correct, so our guess T(n) = (n * (n + 1)) / 2 is the solution for the given recurrence relation.

Iteration Method

Iteration: Start with the given initial conditions and use the relation to calculate subsequent terms until the desired term is found or a pattern emerges for a general solution.

Example :)

Fibonacci Series:

Initial conditions: F(0) = 0, F(1) = 1.

Recurrence relation: F(n) = F(n-1) + F(n-2).

Using iteration method:

F(2) = F(1) + F(0) = 1 + 0 = 1 F(3) = F(2) + F(1) = 1 + 1 = 2 F(4) = F(3) + F(2) = 2 + 1 = 3 F(5) = F(4) + F(3) = 3 + 2 = 5 F(6) = F(5) + F(4) = 5 + 3 = 8

And so on.....

Generating Functions

Generating functions are a technique used to solve recurrence relations by transforming them into a different mathematical domain. To change the recurrence relation into a generating function, typically as a power series, you'll need to manipulate the function so you can find a closed-form expression for the sequence.

Example :)

Example: Consider the recurrence relation T(n) = T(n-1) + 1, with T(0) = 0. Let G(x) be the generating function for the sequence T(n):

G(x) = T(0) + T(1)x + T(2)x^2 + T(3)x^3 + ...

We can multiply both sides of the recurrence relation by x^n and sum over all n:
Σ(T(n) x^n) = Σ(T(n-1) x^n) + Σ(x^n)

G(x) - T(0) = x * G(x) + (1 / (1 - x))

Substitute T(0) = 0 and solve for G(x):

G(x) = 1 / (1 - x)^2

Now, we can use the power series expansion of (1 - x)^(-2) to find the closed-form expression for T(n):

(1 - x)^(-2) = 1 + 2x + 3x^2 + 4x^3 + ...

Thus, T(n) = n + 1 for n = 0, 1, 2, .

Relationship between Recurrence Relation and Dynamic Programming

Recurrence Relations and Dynamic Programming share a close relationship, as Dynamic Programming uses Recurrence Relations to break complex problems into simpler subproblems. This approach enhances efficiency by storing the results of subproblems, preventing redundant computations and ensuring a faster solution. Understanding this connection is essential for mastering Data Structures and Algorithms.

Congress! 😍

Please comment like it will motivates me for writing more blogs