*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.

Part 01 Recurrence Relation- Click me

Part 02 Linear Recurrence Relation- Click me

Part 03 Homogeneous and Particular Solutions- Click me

Part 04 Total solutions and problem- Click me

Part 01 Recurrence Relation- Click me

Part 02 Linear Recurrence Relation- Click me

Part 03 Homogeneous and Particular Solutions- Click me

Part 04 Total solutions and problem- Click me

## No comments:

## Post a Comment

Please do not enter any spam link in the comment box and use English and Hindi language for comment.