Recurrence Relation and Generating Function: Introduction to Recurrence Relation and Recursive Algorithms

Definition

A recurrence relation is an equation that defines a sequence $a_0, a_1, a_2, \dots$ by expressing each term $a_n$ as a function of one or more preceding terms, along with initial conditions.

For example:

$$a_n = a_{n-1} + a_{n-2}, \quad n \ge 2$$ with $$a_0 = 0,\quad a_1 = 1$$ is a recurrence relation, and it defines the Fibonacci sequence.

A generating function for a sequence $\{a_n\}$ is a formal power series:

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

This series acts as an algebraic representation of the sequence. By manipulating $G(x)$, we can often derive formulas for $a_n$.

A recursive algorithm is an algorithm that solves a problem by solving smaller instances of the same problem and combining the results. Recursive algorithms are closely linked to recurrence relations because their time complexity is often described using recurrences.

---

Main Content

1. Recurrence Relations

Meaning and structure

A recurrence relation specifies how to generate a sequence step by step from earlier values. It is especially useful when a quantity depends on previous outcomes, such as counting paths, arranging objects, or computing algorithmic cost. A recurrence relation usually includes:

• a rule connecting terms,
• one or more initial conditions,
• and sometimes boundary conditions.

Example: $$a_n = 2a_{n-1} + 3,\quad a_0 = 1$$ This means each term is obtained from the previous term by multiplying by 2 and adding 3.

Types of recurrence relations

Recurrence relations may be:

• Linear or non-linear
• Homogeneous or non-homogeneous
• First-order or higher-order
• Constant coefficient or variable coefficient

Examples:

• First-order linear: $a_n = 3a_{n-1} + 2$
• Second-order linear: $a_n = a_{n-1} + a_{n-2}$
• Non-linear: $a_n = a_{n-1}^2 + 1$

These classifications matter because different solution methods apply to different types.

Common examples of recurrence relations

1. Fibonacci sequence

$$F_n = F_{n-1} + F_{n-2},\quad F_0=0,\;F_1=1$$ This models growth patterns, branching processes, and combinatorial counting.

2. Arithmetic sequence

$$a_n = a_{n-1} + d$$ where $d$ is constant.

3. Geometric sequence

$$a_n = r a_{n-1}$$ where $r$ is constant.

Why recurrence relations are important

• They describe many real-world and mathematical processes naturally.
• They are essential in algorithm analysis.
• They help in counting combinatorial structures such as binary strings, tilings, and lattice paths.

---

2. Generating Functions

Definition and idea

A generating function converts a sequence into a single algebraic object: $$G(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots$$ The coefficient of $x^n$ stores the term $a_n$. This turns a sequence into a formal series that can be manipulated like an algebraic expression.

Purpose and usefulness

Generating functions are used to:

• solve recurrence relations,
• obtain explicit formulas,
• count combinatorial objects,
• derive identities,
• and model recursive structures.

Example:
For the sequence $1,1,1,1,\dots$, $$G(x) = 1+x+x^2+x^3+\cdots = \frac{1}{1-x}$$ for $|x|<1$ in analytic terms.

Types of generating functions

1. Ordinary generating function (OGF)

$$G(x)=\sum_{n=0}^{\infty} a_n x^n$$ Most common in combinatorics.

2. Exponential generating function (EGF)

$$E(x)=\sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$$ Useful when arrangements and labeled objects are involved.

Example: Fibonacci generating function

Let $$F(x)=\sum_{n=0}^{\infty}F_nx^n$$ Using the recurrence $F_n=F_{n-1}+F_{n-2}$, one obtains: $$F(x)=\frac{x}{1-x-x^2}$$ This compact expression allows us to derive formulas for Fibonacci numbers.

Key algebraic operations on generating functions

• Shifting sequences: $$\sum_{n=0}^{\infty} a_{n-1}x^n = xG(x)$$

• Multiplying by constants

• Adding series
• Extracting coefficients

These operations mirror how sequence terms shift and combine under recurrence relations.

---

3. Recursive Algorithms and Their Relation to Recurrences

What a recursive algorithm is

A recursive algorithm solves a problem by calling itself on smaller subproblems until a base case is reached. This mirrors the mathematical structure of recurrence relations.

Example: factorial $$n! = n \cdot (n-1)!$$ with base case $0!=1$.

How recurrence relations describe time complexity

If an algorithm divides a problem into smaller parts, its running time $T(n)$ is often expressed recursively.

Example:

• A linear recursive algorithm might satisfy: $$T(n)=T(n-1)+c$$

• Divide-and-conquer algorithms often satisfy: $$T(n)=2T(n/2)+n$$

These recurrences are solved to estimate efficiency.

Example: Binary search

Binary search halves the search space at each step. Its recurrence is: $$T(n)=T(n/2)+c$$ with base case $T(1)=c$.

This leads to: $$T(n)=O(\log n)$$

Example: Merge sort

Merge sort divides the array into two halves, sorts both recursively, and merges them: $$T(n)=2T(n/2)+n$$ This solves to: $$T(n)=O(n\log n)$$

Recursive process and base case

A recursive algorithm must have:

Base case

• : stopping condition

Recursive case

• : smaller subproblem

Combination step

• : building the final answer

Without a base case, recursion continues indefinitely.

Relationship between recursion and recurrence

• Recursion is a computational method.
• A recurrence is a mathematical description of that method.
• Generating functions can often be used to solve recurrences that arise from recursive algorithms.

---

Working / Process

1. Formulate the sequence or problem recursively

Identify how the current term or problem depends on previous terms or smaller subproblems. Write the recurrence relation clearly, and include the initial conditions or base cases.

2. Choose a solution method

Depending on the type of recurrence, solve it by:

• direct expansion,
• substitution,
• characteristic equation,
• iteration,
• or generating functions.

3. Convert to generating function and extract results

If using generating functions, define the series $G(x)$, apply the recurrence to build an equation in $G(x)$, solve for $G(x)$, and then extract coefficients to obtain an explicit formula or combinatorial count.

---

Advantages / Applications

Simplifies complex counting problems

Recurrence relations and generating functions make it easier to count arrangements, partitions, paths, and combinatorial structures systematically.

Helps analyze recursive algorithms

They provide a precise way to measure running time, space usage, and growth behavior of recursive and divide-and-conquer algorithms.

Useful in combinatorics and discrete structures

They are widely used in partition theory, graph counting, lattice path enumeration, and the study of ordered structures related to posets and combinatorial constructions.

---

Summary

• Recurrence relations define sequences using earlier terms.
• Generating functions represent sequences as power series for algebraic manipulation.
• Recursive algorithms naturally lead to recurrence relations in analysis.

Important terms to remember: recurrence relation, initial condition, generating function, ordinary generating function, recursive algorithm, base case.