## 3/20/23

### What is Recurrence Relation?

Recurrence Relation: Definition Part-01

Unit-05

Recurrence Relation: Definition

Examples (Fibonacci, Factorial etc.),

Linear recurrence relations with constants coefficients –

Homogenous solutions

Particular solutions

Total solutions

Problems.

Recurrence Relation: Definition

1.    A recurrence relation is a mathematical equation that defines a sequence of numbers, where each term of the sequence is expressed as a function of one or more preceding terms.

2.    In other words, a recurrence relation is a way of defining a sequence by recursively calculating each term based on the previous terms in the sequence.

3.    Recurrence relations are commonly used in many areas of mathematics, computer science, and engineering, including number theory, combinatorics, graph theory, algorithms, and optimization.

4.    They are particularly useful for analysing the time complexity of algorithms, as well as for modelling dynamic systems that evolve over time.

5.    Recurrence relations can be linear or nonlinear, homogeneous or non-homogeneous, and have different degrees of complexity.

6.    Solving a recurrence relation involves finding a closed-form solution that expresses each term of the sequence as a function of the initial conditions and the recurrence equation itself.

Examples of Recurrence Relation: -

Here are some examples of recurrence relations:

1.              Fibonacci sequence:

a.    The Fibonacci sequence is a well-known example of a recurrence relation.

b.    It is defined by the recurrence relation:

F(n) = F(n-1) + F(n-2), where F(0) = 0 and F(1) = 1. This defines the sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

2.              Factorial function:

a.    The factorial function is defined recursively as follows:

n! = n * (n-1)!, where 0! = 1.

b.    For example, 4! = 4 * 3 * 2 * 1 = 24.

3.              Towers of Hanoi:

a.    The Towers of Hanoi puzzle can be defined recursively as follows:

b.    To move n disks from tower A to tower C using tower B:

i.     Move n-1 disks from tower A to tower B using tower C

ii.     Move the largest disk from tower A to tower C.

iii.     Move the n-1 disks from tower B to tower C using tower A.

4.              Merge sort:

a.    The merge sort algorithm is defined recursively as follows:

b.    To sort an array A[1..n]:

i.     If n ≤ 1, return A

ii.     Split A into two subarrays, A[1..n/2] and A[n/2+1..n]

iii.     Recursively sort each subarray

iv.     Merge the two sorted subarrays into a single sorted array.

These are just a few examples of the many different types of recurrence relations that exist in mathematics and computer science.