Back To Top

Unit-2: Recurrence Relations

1. Recurrence Relations

1. What is a Recurrence Relation?

A recurrence relation is an equation that defines a sequence based on previous terms in the sequence.

It expresses the nth term of a sequence as a function of its earlier terms.

Example:

Fibonacci Sequence:

aₙ = aₙ₋₁ + aₙ₋₂, with initial conditions a₀ = 0, a₁ = 1.

2. Types of Recurrence Relations

3. Solving Recurrence Relations

Example 1: Linear Homogeneous

aₙ = 2aₙ₋₁, a₀ = 3

Solution:

General Solution: aₙ = 3(2ⁿ)

Example 2: Non-Homogeneous

aₙ = aₙ₋₁ + 2, a₀ = 1

Solution:

General Solution: aₙ = 2n + 1

4. Recurrence Tree Method

Break down recursive calls like a tree to visualize the sequence.

Useful for analyzing recursive algorithms, like mergesort or binary search.

5. Master Theorem (For Algorithm Complexity)

Helps solve recurrence relations for divide-and-conquer algorithms.

T(n) = aT(n/b) + f(n)

Example: Mergesort → T(n) = 2T(n/2) + n ⇒ O(n log n)

2. Modeling with Recurrence Relations

1. What is Modeling with Recurrence Relations?

Modeling with recurrence relations involves describing a real-world process or problem using recursive formulas. You define how a system evolves over time based on previous states.

2. Real-World Examples

Example 1: Population Growth

Suppose a population grows by a fixed percentage every year, and we start with an initial population.

Recurrence Relation:

Pₙ = Pₙ₋₁ + rPₙ₋₁

Where:

Solution:

This is a geometric sequence, so we get:

Pₙ = P₀(1 + r)ⁿ

Example 2: Rabbit Breeding (Fibonacci Sequence)

A pair of rabbits produces another pair every month starting from their second month. How many pairs will there be after n months?

Recurrence Relation:

Fₙ = Fₙ₋₁ + Fₙ₋₂

With initial conditions: F₀ = 0, F₁ = 1

Solution:

This is the famous Fibonacci sequence:

F₀, F₁, F₂, F₃, F₄, F₅... = 0, 1, 1, 2, 3, 5...

3. Algorithmic Complexity (Recursive Algorithms)

Recurrence relations are crucial for analyzing recursive algorithms.

Example: Binary Search

Binary search splits the array in half at each step, so the runtime can be modeled with:

T(n) = T(n/2) + c

Where:

Solution (Using Master Theorem):

T(n) = O(log n)

4. Resource Allocation

Imagine a factory produces widgets, but each widget needs components from the previous batch.

Recurrence Relation:

Wₙ = 2Wₙ₋₁ + 10

Where:

Solution (Iteration):

W₀ = 5

W₁ = 2(5) + 10 = 20

W₂ = 2(20) + 10 = 50

General Solution: Wₙ = 5(2ⁿ) + 10(2ⁿ - 1)

5. Epidemic Spread (SIR Model)

Modeling disease spread with recurrence relations:

Recurrence Relation:

Sₙ = Sₙ₋₁ - βSₙ₋₁Iₙ₋₁

Iₙ = Iₙ₋₁ + βSₙ₋₁Iₙ₋₁ - γIₙ₋₁

Rₙ = Rₙ₋₁ + γIₙ₋₁

Where:

Solution:

This creates a recursive model for predicting the spread of disease over time.

3. Homogeneous Linear Recurrence Relations with Constant Coefficients

1. What is a Homogeneous Linear Recurrence Relation?

A homogeneous linear recurrence relation expresses each term as a linear combination of previous terms, with constant coefficients, and without any external (non-recursive) terms.

General Form:

aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + ... + cₖaₙ₋ₖ

Where:

2. Example 1: Second-Order Linear Relation

Example: aₙ = 3aₙ₋₁ - 2aₙ₋₂

Initial conditions: a₀ = 2, a₁ = 3

Step 1: Find the Characteristic Equation

Replace aₙ with rⁿ:

r² - 3r + 2 = 0

Factor the equation:

(r - 1)(r - 2) = 0

Roots: r = 1, r = 2

Step 2: General Solution

aₙ = A(1)ⁿ + B(2)ⁿ

Step 3: Use Initial Conditions

Substitute the initial values:

Solve the system of equations:

Solution:

Step 4: Final Solution

aₙ = (1)(1)ⁿ + (1)(2)ⁿ

aₙ = 1 + 2ⁿ

3. Higher-Order Example

Example: aₙ = 4aₙ₋₁ - 5aₙ₋₂ + aₙ₋₃

Initial conditions: a₀ = 1, a₁ = 2, a₂ = 4

Step 1: Characteristic Equation

r³ - 4r² + 5r - 1 = 0

Step 2: Solve the Characteristic Equation

Let’s say the roots are r₁, r₂, r₃ (you can solve using factorization or trial roots).

Suppose roots: r = 1, 1, 2

Step 3: General Solution

aₙ = (A + Bn)(1)ⁿ + C(2)ⁿ

(The repeated root introduces the n term.)

Step 4: Use Initial Conditions to Find Coefficients

Plug in initial conditions to find A, B, and C.

4. Solving Non-Homogeneous Recurrence Relations Using the Method of Inverse Operator

1. What is a Non-Homogeneous Recurrence Relation?

A non-homogeneous recurrence relation is a relation where the right-hand side is not zero — it includes an external function (forcing term).

General Form:

aₙ - c₁aₙ₋₁ - c₂aₙ₋₂ - ... - cₖaₙ₋ₖ = f(n)

Or using the shift operator (E):

F(E)aₙ = f(n)

Where:

2. Steps to Solve Using the Inverse Operator

  1. Find the Complementary Solution (aₙᶜ) by solving the homogeneous part (F(E)aₙ = 0).
  2. Find the Particular Solution (aₙᵖ) using the inverse operator:
    aₙᵖ = F(E)⁻¹(f(n))
  3. General Solution: aₙ = aₙᶜ + aₙᵖ

3. Example 1: Simple Non-Homogeneous Relation

Example: aₙ - 3aₙ₋₁ = 2ⁿ

Initial condition: a₀ = 1

Step 1: Solve the Homogeneous Part

aₙ - 3aₙ₋₁ = 0 → Characteristic equation: r - 3 = 0

Root: r = 3

Complementary solution: aₙᶜ = A(3)ⁿ

Step 2: Find the Particular Solution

f(n) = 2ⁿ, so use the inverse operator:

aₙᵖ = (1 / (1 - 3E⁻¹))(2ⁿ)

Substitute E(2ⁿ) = 2 × 2ⁿ:

aₙᵖ = (1 / (1 - 3/2))(2ⁿ)

aₙᵖ = (1 / (-1/2))(2ⁿ)

aₙᵖ = -2(2ⁿ)

Step 3: General Solution

aₙ = aₙᶜ + aₙᵖ

aₙ = A(3)ⁿ - 2(2ⁿ)

Step 4: Use Initial Condition

a₀ = 1 → A(3)⁰ - 2(2)⁰ = 1

A - 2 = 1 → A = 3

Final Solution:

aₙ = 3(3)ⁿ - 2(2ⁿ)

4. Example 2: Polynomial Non-Homogeneous Part

Example: aₙ - 2aₙ₋₁ + aₙ₋₂ = n

Step 1: Solve the Homogeneous Part

Characteristic equation: r² - 2r + 1 = 0

(r - 1)² = 0 → Double root r = 1

Complementary solution: aₙᶜ = (A + Bn)(1)ⁿ

Step 2: Find the Particular Solution

f(n) = n, so try a polynomial solution:

aₙᵖ = Cn² + Dn + E

Substitute into the recurrence relation and equate coefficients to solve for C, D, and E.

Step 3: General Solution

aₙ = (A + Bn)(1)ⁿ + aₙᵖ

5. Solving Recurrence Relations Using Generating Functions

1. What is a Generating Function?

A generating function is a way to encode a sequence as a power series. It helps turn recurrence relations into algebraic equations, which we can solve and then extract the sequence from.

The generating function of a sequence {aₙ} is:

G(x) = a₀ + a₁x + a₂x² + a₃x³ + ... = ∑ aₙxⁿ

2. Steps to Solve a Recurrence Relation Using Generating Functions

  1. Set up the generating function: Define G(x) as the series representation of the sequence.
  2. Transform the recurrence relation: Use the properties of generating functions (like shifting indices) to turn the recurrence into an equation in terms of G(x).
  3. Solve for G(x): Use algebra to isolate G(x).
  4. Expand G(x) back to a series: Use partial fraction decomposition or series expansion to find the explicit formula for aₙ.

3. Example 1: Simple Linear Recurrence Relation

Example: aₙ - aₙ₋₁ = 1 (for n ≥ 1), with a₀ = 2

Step 1: Define the Generating Function

G(x) = ∑ aₙxⁿ

Step 2: Use the Recurrence Relation

aₙ = aₙ₋₁ + 1 → Shift the index:

∑ aₙxⁿ = ∑ aₙ₋₁xⁿ + ∑ xⁿ

G(x) = xG(x) + ∑ xⁿ

Step 3: Solve for G(x)

G(x) - xG(x) = ∑ xⁿ = (1 / (1 - x))

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

G(x) = (1 / (1 - x)²) + (2 / (1 - x))

Step 4: Expand as a Series

G(x) = ∑ (n + 1)xⁿ + 2∑ xⁿ

aₙ = n + 1 + 2 = n + 3

Final Solution:

aₙ = n + 3

4. Example 2: Second-Order Linear Recurrence

Example: aₙ - 3aₙ₋₁ + 2aₙ₋₂ = 0, with a₀ = 1, a₁ = 2

Step 1: Define the Generating Function

G(x) = ∑ aₙxⁿ

Step 2: Use the Recurrence Relation

aₙ - 3aₙ₋₁ + 2aₙ₋₂ = 0 → Translate using G(x):

G(x) - 3xG(x) + 2x²G(x) = a₀ + (a₁ - 3a₀x)

Step 3: Solve for G(x)

G(x)(1 - 3x + 2x²) = 1 + 2x

G(x) = (1 + 2x) / (1 - 3x + 2x²)

Factor the denominator:

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

Step 4: Expand with Partial Fractions

Use partial fraction decomposition:

G(x) = A / (1 - x) + B / (1 - 2x)

Solve for A and B:

A = 1, B = 1

Step 5: Extract the Sequence

G(x) = ∑ xⁿ + ∑ 2ⁿxⁿ

aₙ = 1 + 2ⁿ

Final Solution:

aₙ = 1 + 2ⁿ

5. Why Use Generating Functions?