Skip to content
Home » Principle Recurrence relations

Principle Recurrence relations

Here is a clear, simple, and exam-oriented explanation of Recurrence Relations — perfect for BCA/MCA/Engineering/Discrete Mathematics exams.

⭐ Recurrence Relations – Introduction

A recurrence relation (or recursive relation) is an equation that defines each term of a sequence based on previous terms.

It describes how one term relates to earlier terms.

⭐ Definition

A recurrence relation for a sequence ( {a_n} ) is an equation of the form:

[
a_n = f(a_{n-1}, a_{n-2}, \ldots, a_{n-k})
]

where:

  • (a_n) = nth term
  • (f) = function involving earlier terms
  • k = order of the recurrence

You also need initial conditions (starting values) to get the complete sequence.

⭐ Why Recurrence Relations Are Important?

Used in:

✔ Algorithm analysis (time complexity)
✔ Data structures
✔ Computer science
✔ Dynamic programming
✔ Counting problems
✔ Fibonacci sequence
✔ Divide-and-conquer algorithms

⭐ 1️⃣ Basic Examples of Recurrence Relations

Example 1: Fibonacci Sequence

[
F_n = F_{n-1} + F_{n-2}
]
with
[
F_0 = 0,; F_1 = 1
]

Example 2: Factorial

[
n! = n \cdot (n-1)!
]
with
[
1! = 1
]

Example 3: Arithmetic Sequence

[
a_n = a_{n-1} + d
]

Example 4: Geometric Sequence

[
a_n = r \cdot a_{n-1}
]

⭐ 2️⃣ Types of Recurrence Relations

A. Linear Recurrence Relations

A recurrence relation is linear if:

[
a_n = c_1a_{n-1} + c_2a_{n-2} + \cdots + c_ka_{n-k}
]

Coefficients (c_1, c_2, \ldots, c_k) are constants.

Example:

[
a_n = 3a_{n-1} – 2a_{n-2}
]

B. Homogeneous Recurrence Relations

A recurrence is homogeneous if the right-hand side has no extra term.

Example:

[
a_n = 2a_{n-1} + 3a_{n-2}
]

C. Non-Homogeneous Recurrence Relations

Includes additional functions or constants:

[
a_n = 2a_{n-1} + 3a_{n-2} + 5
]

or

[
a_n = a_{n-1} + n
]

⭐ 3️⃣ Solving Linear Homogeneous Recurrence Relations

The standard way to solve:

[
a_n = c_1a_{n-1} + c_2a_{n-2}
]

is the characteristic equation method:

  1. Assume solution of form (a_n = r^n)
  2. Substitute into recurrence
  3. Solve for r using characteristic equation

Example

Solve:

[
a_n = 3a_{n-1} – 2a_{n-2}
]

Characteristic equation:

[
r^2 = 3r – 2
\Rightarrow r^2 – 3r + 2 = 0
]

Factor:

[
(r-1)(r-2) = 0
\Rightarrow r = 1, 2
]

General solution:

[
a_n = A \cdot 1^n + B \cdot 2^n
]

Use initial conditions to find A and B.

⭐ 4️⃣ Divide-and-Conquer Recurrence Relations (from Algorithms)

Examples:

  • Binary search:
    [
    T(n) = T(n/2) + 1
    ]
  • Merge sort:
    [
    T(n) = 2T(n/2) + n
    ]
  • Tower of Hanoi:
    [
    T(n) = 2T(n-1) + 1
    ]

These are solved using the Master Theorem or expansion.

⭐ 5️⃣ First-Order Recurrence Relations

Recurrence involving only one previous term:

[
a_n = f(a_{n-1})
]

Example:

[
a_n = 3a_{n-1} + 2
]

Solve by iteration.

⭐ 6️⃣ Second-Order Recurrence Relations

Recurrence involving two previous terms:

[
a_n = f(a_{n-1}, a_{n-2})
]

Example:

[
a_n = 5a_{n-1} – 6a_{n-2}
]

⭐ 7️⃣ Special Applications in Combinatorics

✔ Counting ways to climb n stairs

[
T(n) = T(n-1) + T(n-2)
]

✔ Counting tilings

[
T(n) = T(n-1) + T(n-2)
]

✔ Number of binary strings with no consecutive 1s

[
a_n = a_{n-1} + a_{n-2}
]

⭐ Quick Exam-Oriented Summary

Definition:

A recurrence relation defines a sequence using earlier terms.

Examples:

Fibonacci, factorial, arithmetic, geometric.

Types:

  • Linear
  • Homogeneous
  • Non-homogeneous
  • First order
  • Second order
  • Divide-and-conquer

Solution methods:

  • Characteristic equation
  • Iteration
  • Master theorem (algorithms)

Uses:

Algorithms, counting, sequences, dynamic programming.