Discrete Structure (CS-302) - Unit 8 Short Notes

Introduction

UNIT 8: Recurrence Relations and Generating Functions

1. Introduction to Recurrence Relations and Recursive Algorithms

Definition of Recurrence Relations

[!IMPORTANT]

A recurrence relation is an equation that recursively defines a sequence, where each term is expressed as a function of its preceding terms.

Mathematically, a recurrence relation for a sequence $\{a_n\}$ is written as:

$$ a_n = f\left(a_{n-1}, a_{n-2}, \ldots, a_{n-k}\right), \quad n > k $$

where $f$ is a function and $k$ is the order of the relation (number of previous terms involved).

Examples of Recurrence Relations

• Fibonacci sequence: $F_n = F_{n-1} + F_{n-2}$ (with $F_0=0, F_1=1$)

• Factorial: $n! = n \cdot (n-1)!$, with $0! = 1$

• Arithmetic sequence: $a_n = a_{n-1} + d$

Classification: Linear vs. Nonlinear, Homogeneous vs. Non-Homogeneous

Definition and Examples of Recursive Algorithms

[!IMPORTANT]

A recursive algorithm is an algorithm that calls itself to solve a smaller instance of the same problem, with defined base condition(s) to terminate recursion.

Example:

• Factorial calculation:

  
  int factorial(int n) {
  
      if(n == 0) return 1;
  
      else return n * factorial(n-1);
  
  }
  
  

• Binary Search (array-based, recursive)

Applications of Recurrence Relations and Recursive Algorithms

• Mathematics: Counting problems, combinatorics, sequence analysis.

• Computer Science: Analysis of algorithm complexity (e.g., merge sort), dynamic programming.

• Discrete Modelling: Population models, financial calculations.

[!TIP]

Most exam questions ask you to write, classify, or solve recurrence relations, or connect them with recursive algorithms (especially sorting/searching).

2. Linear Recurrence Relations with Constant Coefficients

Definition & Order

[!IMPORTANT]

A linear recurrence relation with constant coefficients is an equation of the form:

$$ > a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} + f(n) > $$

where all $c_i$ are constants, and $f(n)$ is a function of $n$ (zero in the homogeneous case).

Order: The largest backward step involved (i.e., $k$ in the above).

Homogeneous Recurrence Relations

The homogeneous linear recurrence relation ($f(n)=0$) of order $k$:

$$ a_n + c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k} = 0 $$

Characteristic Equation [DERIVATION]

For the homogeneous case:

1. Assume a solution of the form: $a_n = r^n$

2. Substitute into the homogeneous recurrence:

$$ r^n + c_1 r^{n-1} + c_2 r^{n-2} + \cdots + c_k r^{n-k} = 0 $$

3. Divide both sides by $r^{n-k}$ (if $r\neq 0$):

$$ r^k + c_1 r^{k-1} + c_2 r^{k-2} + \cdots + c_k = 0 $$

• This is the characteristic equation.

Solution Techniques [DERIVATION]

• Find roots ($r_1, r_2, ..., r_k$) of the characteristic equation.

• The general solution:

  • If all $r_i$ are distinct:

$$ a_n = A_1 r_1^n + A_2 r_2^n + \cdots + A_k r_k^n $$

- If some roots are repeated: Multiply by $n$ for each repeated root ($n^i r^n$).

- If complex roots: Convert to real using Euler's formula.

Example Problem [NUMERICAL]

Problem: Solve the recurrence $a_n - 3a_{n-1} + 2a_{n-2} = 0$, with $a_0 = 2$, $a_1 = 3$.

Solution:

1. Characteristic equation:

$$ r^2 - 3r + 2 = 0 $$

2. Factor:

$$ (r-1)(r-2) = 0 \Rightarrow r_1 = 1, r_2 = 2 $$

3. General solution:

$$ a_n = A \cdot 1^n + B \cdot 2^n = A + B \cdot 2^n $$

4. Use initial conditions:

   • $a_0 = A + B = 2$

   • $a_1 = A + 2B = 3$

   Subtract: $(a_1 - a_0): (A + 2B) - (A + B) = B = 1$

   Thus, $B=1$, $A=2-B=1$.

5. Final answer:

$$ \boxed{a_n = 1 + 2^n} $$

[!TIP]

Always check: order, write characteristic equation, solve for roots, use initial conditions.

Non-Homogeneous (Particular) Solutions

Here, $f(n) \neq 0$. The recurrence:

$$ a_n + c_1 a_{n-1} + ... + c_k a_{n-k} = f(n) $$

Particular Solution Methods (Undetermined Coefficients) [DERIVATION]

1. Guess a form for a particular solution $a_n^p$ similar in type to $f(n)$ (polynomial, exponential, etc.).

2. Substitute back into the recurrence and solve for coefficients.

3. Add to general solution of homogeneous part.

Sample Types & Forms:

Worked Example [NUMERICAL NEEDED]

Problem: Solve $a_n - a_{n-1} = 2$, with $a_0 = 1$.

Step 1: Homogeneous part: $a_n - a_{n-1}=0$

Characteristic equation: $r-1=0$, so $r=1$.

General solution to homogeneous: $a_n^h = A$.

Step 2: Guess a particular solution.

$f(n) = 2$ (constant), guess $a_n^p = P$.

Substitute: $a_n^p - a_{n-1}^p = 2 \implies P - P = 2 \implies 0 = 2 \quad$ (Contradiction!)

When the guess matches a root, use $P n$ instead.

Try $a_n^p = P n$.

Substitute back: $P n - P(n-1) = 2$ $P n - P n + P = 2$ $P = 2 \implies a_n^p = 2n$

General solution: $a_n = a_n^h + a_n^p = A + 2n$

Use $a_0 = 1$: $1 = A + 0 \implies A = 1$

$\boxed{a_n = 1 + 2n}$

[!TIP]

If a candidate for the particular solution is a solution to the homogeneous part, multiply by $n$ (once for each repetition).

3. Total Solutions of Recurrence Relations

General Solution Structure

[!IMPORTANT]

The general (total) solution of a linear non-homogeneous recurrence relation:

$$ > a_n = a_n^h + a_n^p > $$

where $a_n^h$ is the general solution to the homogeneous part, and $a_n^p$ is a particular solution to the non-homogeneous part.

Steps to Find the Total Solution [DERIVATION]

1. Solve the homogeneous equation:

$$ a_n + c_1 a_{n-1} + \cdots + c_k a_{n-k} = 0 $$

• Find its general solution ($a_n^h$) using the characteristic equation method.

2. Find a particular solution ($a_n^p$) matching the form of the non-homogeneous part.

3. Add both parts:

$$ a_n = a_n^h + a_n^p $$

4. Use initial conditions to determine constants in the homogeneous solution.

Example (Total Solution) [NUMERICAL]

Problem: Solve $a_n - 2a_{n-1} = 3^n$, $a_0 = 2$.

Step 1: Homogeneous part

• $a_n - 2a_{n-1} = 0 \implies$ characteristic eqn: $r-2=0 \implies r=2$

• General solution: $a_n^h = A \cdot 2^n$

Step 2: Particular solution

• $f(n) = 3^n$, guess: $a_n^p = P \cdot 3^n$

• Substitute:

$$ P \cdot 3^n - 2P \cdot 3^{n-1} = 3^n \\ P \cdot 3^n - 2P \cdot 3^{n-1} = 3^n \\ \text{Divide by } 3^{n-1}:\\ 3P - 2P = 3 \implies P=3 $$

• Particular solution: $a_n^p = 3 \cdot 3^n$

Step 3: General Solution

$$ a_n = A \cdot 2^n + 3 \cdot 3^n $$

Step 4: Use Initial Condition

$a_0 = 2 \implies A \cdot 2^0 + 3 \cdot 3^0 = A + 3 = 2 \implies A = -1$

Final Answer:

$$ \boxed{a_n = -1 \cdot 2^n + 3 \cdot 3^n} $$

4. Generating Functions and Solution by the Method of Generating Functions

Definition of Generating Function

[!IMPORTANT]

The generating function of a sequence $\{a_n\}$ is the formal power series:

$$ > G(a_n; x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots = \sum_{n=0}^{\infty} a_n x^n > $$

Ordinary Generating Functions [DERIVATION]

• The ordinary generating function for $\{a_n\}$ is:

$$ A(x) = \sum_{n=0}^\infty a_n x^n $$

• For example, for the sequence $1, 1, 1, \ldots$, $A(x) = 1 + x + x^2 + \cdots = \frac{1}{1-x}$ for $|x|<1$.

Formation and Properties of Generating Functions

• Linearity: The generating function of $a_n + b_n$ is the sum of their generating functions.

• Shift Property: The generating function for $a_{n+1}$ is $\frac{A(x) - a_0}{x}$.

• Multiplication by $n$: The generating function for $n a_n$ is $x \frac{d}{dx} A(x)$.

Using Generating Functions to Solve Recurrence Relations [DERIVATION]

General method:

1. Write the recurrence (with initial conditions).

2. Multiply both sides by $x^n$ and sum for $n=0$ to $\infty$.

3. Manipulate the sums/algebra to express everything in terms of the generating function $A(x)$.

4. Solve the resulting algebraic equation for $A(x)$.

5. Expand $A(x)$ as a power series to find the general term $a_n$.

Worked Example [NUMERICAL NEEDED]

Problem: Solve $a_n - a_{n-1} = 1$, with $a_0=2$, using generating functions.

Step 1: Multiply by $x^n$ and sum from $n=1$ to $\infty$:

$$ \sum_{n=1}^{\infty} (a_n - a_{n-1}) x^n = \sum_{n=1}^\infty 1 \cdot x^n $$

Left side:

$$ \sum_{n=1}^\infty a_n x^n - \sum_{n=1}^\infty a_{n-1} x^n = [A(x) - a_0] - x A(x) $$

Right side:

$$ \sum_{n=1}^{\infty} x^n = \frac{x}{1-x} $$

Step 2: Put together:

$$ [A(x) - a_0] - x A(x) = \frac{x}{1-x} $$

$$ A(x) - a_0 - x A(x) = \frac{x}{1-x} $$

$$ A(x)(1 - x) = a_0 + \frac{x}{1-x} $$

$$ A(x) = \frac{a_0}{1-x} + \frac{x}{(1-x)^2} $$

Given $a_0 = 2$,

$$ A(x) = \frac{2}{1-x} + \frac{x}{(1-x)^2} $$

Expand using known series:

• $\frac{2}{1-x} = 2 \sum_{n=0}^\infty x^n = \sum_{n=0}^\infty 2 x^n$

• $\frac{x}{(1-x)^2} = \sum_{n=0}^\infty (n+1) x^{n+1} = \sum_{n=1}^\infty n x^n$

Thus,

$$ A(x) = \sum_{n=0}^\infty 2 x^n + \sum_{n=1}^\infty n x^n $$

Collect coefficients for $a_n$ ($n \ge 1$):

$$ a_n = 2 + n, ~\text{for}~ n \geq 1; \quad a_0 = 2 $$

Thus:

$$ \boxed{a_n = n + 2} $$

[!TIP]

Always write out the generating function sums explicitly and manipulate them algebraically. Know the power series for $\frac{1}{1-x}$ and $\frac{1}{(1-x)^2}$ for quick answers.

End of UNIT 8 Notes: Recurrence Relations and Generating Functions.