discrete math recurrence relations examples

Introduction

Table of Contents

• What are Recurrence Relations?
• Types of Recurrence Relations
• Methods for Solving Recurrence Relations
• The Characteristic Equation Method
• The Iteration Method
• The Generating Functions Method
• Common Discrete Math Recurrence Relations Examples
• Fibonacci Sequence
• Factorial Function
• Tower of Hanoi
• Binary Search
• Merge Sort
• Quick Sort
• Counting Binary Strings without Consecutive 1s
• Catalan Numbers
• Solving Specific Discrete Math Recurrence Relations Examples
• Solving a Linear Homogeneous Recurrence Relation
• Solving a Linear Non-Homogeneous Recurrence Relation
• Solving a Recurrence Relation using Iteration
• Applications of Recurrence Relations
• Conclusion

What are Recurrence Relations?

In discrete mathematics, a recurrence relation, also known as a difference equation, is an equation that recursively defines a sequence or multidimensional array. It expresses a term of the sequence as a function of its preceding terms. This recursive definition is vital because it allows us to build up complex sequences from simpler starting points. Think of it as a set of rules that tell you how to get the next number in a sequence if you know the previous ones. For instance, if you know the first few terms and a rule like "add the previous two terms to get the next term," you can generate the entire sequence.

The general form of a recurrence relation is typically $a_n = f(a_{n-1}, a_{n-2}, ..., a_{n-k}, n)$, where $a_n$ is the term at position $n$, and $f$ is a function that depends on the previous $k$ terms and possibly the index $n$. The number $k$ is called the order of the recurrence relation. To uniquely define a sequence using a recurrence relation, we also need initial conditions, also known as base cases. These are specific values for the first few terms of the sequence, such as $a_0$, $a_1$, and so on, up to $a_{k-1}$. Without these base cases, there would be infinitely many sequences satisfying the recursive definition.

Types of Recurrence Relations

Recurrence relations can be categorized based on several properties, which influence the methods used to solve them. Understanding these distinctions is key to applying the correct techniques. The primary classifications revolve around linearity, homogeneity, and the nature of the dependency on the index $n$.

Linear Recurrence Relations

A recurrence relation is linear if each term in the sequence appears only to the first power, and there are no products of terms. The general form of a linear recurrence relation of order $k$ is $a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k} + g(n)$, where $c_1, c_2, ..., c_k$ are constants (or functions of $n$), and $g(n)$ is a function of $n$ that does not involve any terms of the sequence.

Homogeneous vs. Non-Homogeneous Recurrence Relations

A linear recurrence relation is called homogeneous if $g(n) = 0$. In this case, the relation takes the form $a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k}$. If $g(n)$ is not identically zero, the relation is non-homogeneous. The presence of $g(n)$ introduces additional complexity when solving the relation.

Constant Coefficients vs. Variable Coefficients

If the coefficients $c_1, c_2, ..., c_k$ in a linear recurrence relation are constants, it is a recurrence relation with constant coefficients. These are generally easier to solve than those with variable coefficients, where the coefficients are functions of $n$. Most introductory examples and common algorithms involve constant coefficients.

Order of a Recurrence Relation

The order of a recurrence relation is the difference between the largest and smallest indices of the sequence terms involved in the definition. For example, in $a_n = 2a_{n-1} + a_{n-2}$, the indices are $n$, $n-1$, and $n-2$. The largest index is $n$ and the smallest is $n-2$, so the order is $n - (n-2) = 2$. Higher-order relations typically require more sophisticated solving techniques.

Methods for Solving Recurrence Relations

Solving recurrence relations means finding a closed-form expression for $a_n$, an explicit formula that directly calculates the $n$-th term without needing to compute all the preceding terms. Several techniques exist, each suited to different types of recurrence relations. Understanding these methods is key to efficiently analyzing the behavior of sequences and algorithms.

The Characteristic Equation Method

This is a powerful method for solving linear homogeneous recurrence relations with constant coefficients. The process involves constructing a characteristic equation, which is a polynomial equation derived from the recurrence relation. For a relation of the form $a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k}$, the characteristic equation is $r^k - c_1 r^{k-1} - c_2 r^{k-2} - ... - c_k = 0$. The roots of this equation determine the general form of the solution. If the roots are distinct, say $r_1, r_2, ..., r_k$, the general solution is $a_n = A_1 r_1^n + A_2 r_2^n + ... + A_k r_k^n$, where $A_i$ are constants determined by the initial conditions.

If there are repeated roots or complex roots, the form of the general solution changes. For a root $r$ with multiplicity $m$, the terms in the solution will be of the form $(A_0 + A_1 n + ... + A_{m-1} n^{m-1}) r^n$. This method is highly systematic for a specific class of recurrence relations.

The Iteration Method

The iteration method, also known as unrolling or substitution, involves repeatedly substituting the recurrence relation into itself. This process generates a pattern that can often be generalized into a closed-form solution. It's an intuitive method that works well for simpler recurrence relations, especially those of order one or two.

The steps typically involve:

• Write out the first few terms of the sequence by applying the recurrence relation.
• Substitute the definition of a term into the expression for the next term.
• Continue this substitution process until a pattern emerges.
• Identify the pattern and express it as a closed-form formula, often involving summation.
• Verify the formula using mathematical induction.

While insightful, this method can become cumbersome for higher-order relations or complex functions $g(n)$.

The Generating Functions Method

Generating functions provide a more abstract but powerful approach to solving recurrence relations, particularly non-homogeneous ones and those with variable coefficients. A generating function for a sequence $a_0, a_1, a_2, ...$ is a power series $G(x) = a_0 + a_1 x + a_2 x^2 + ... = \sum_{n=0}^{\infty} a_n x^n$. By manipulating the recurrence relation algebraically and substituting the generating function, one can derive an equation for $G(x)$. Solving for $G(x)$ and then finding its power series expansion yields the closed-form solution for $a_n$.

This method requires familiarity with power series manipulation and techniques for finding closed forms of power series, such as geometric series and Taylor series. It's particularly effective for problems where identifying patterns through iteration is difficult.

Common Discrete Math Recurrence Relations Examples

Recurrence relations appear in numerous contexts within discrete mathematics and computer science. Understanding these common examples provides a strong foundation for recognizing and solving similar problems.

Fibonacci Sequence

The Fibonacci sequence is perhaps the most famous example of a recurrence relation. Defined by the rule that each number is the sum of the two preceding ones, starting from 0 and 1. The recurrence relation is:

$F_n = F_{n-1} + F_{n-2}$ for $n \ge 2$

With initial conditions $F_0 = 0$ and $F_1 = 1$. The sequence begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

The closed-form solution for the Fibonacci sequence is given by Binet's formula: $F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$, where $\phi = \frac{1+\sqrt{5}}{2}$ (the golden ratio) and $\psi = \frac{1-\sqrt{5}}{2}$.

Factorial Function

The factorial of a non-negative integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to $n$. The recurrence relation is:

$n! = n \times (n-1)!$ for $n \ge 1$

With the initial condition $0! = 1$. The sequence is: 1, 1, 2, 6, 24, 120, ...

The closed-form expression is simply $n!$. However, the recurrence relation is a fundamental way to define it.

Tower of Hanoi

The Tower of Hanoi puzzle involves moving a stack of disks of different sizes from one peg to another, with the constraint that a larger disk can never be placed on top of a smaller disk. Let $H_n$ be the minimum number of moves required to transfer $n$ disks from the source peg to the destination peg.

To move $n$ disks, we must:

• Move $n-1$ disks from the source peg to the auxiliary peg ( $H_{n-1}$ moves).
• Move the largest disk (the $n$-th disk) from the source peg to the destination peg (1 move).
• Move the $n-1$ disks from the auxiliary peg to the destination peg on top of the largest disk ( $H_{n-1}$ moves).

This leads to the recurrence relation: $H_n = 2H_{n-1} + 1$ for $n \ge 1$, with the initial condition $H_0 = 0$ (or $H_1 = 1$).

The closed-form solution for $H_n$ is $2^n - 1$. This is a classic example of a linear non-homogeneous recurrence relation.

Binary Search

Binary search is an efficient algorithm for finding an item from a sorted list of items. When analyzing the time complexity, we often encounter a recurrence relation. Let $T(n)$ be the time complexity for searching in a list of size $n$. In the worst case, binary search divides the problem into subproblems of roughly half the size.

The recurrence relation for binary search is:

$T(n) = T(n/2) + c$ for $n > 1$

With base case $T(1) = c'$, where $c$ and $c'$ are constants representing the work done outside the recursive calls. This recurrence relation is solved using the Master Theorem or substitution, yielding $T(n) = O(\log n)$.

Merge Sort

Merge sort is a divide-and-conquer sorting algorithm. It divides the input array into two halves, recursively sorts the two halves, and then merges the sorted halves. Let $T(n)$ be the time complexity for merge sort.

The recurrence relation is:

$T(n) = 2T(n/2) + O(n)$

The $2T(n/2)$ represents the time for recursively sorting the two halves, and $O(n)$ represents the time for merging the two sorted halves. Using the Master Theorem, the solution is $T(n) = O(n \log n)$.

Quick Sort

Quick sort is another divide-and-conquer sorting algorithm. The recurrence relation for quick sort is more complex to define precisely because the partition step can result in unbalanced subproblems. In the average case, the pivot selection leads to subproblems of size approximately $n/2$.

Average Case Recurrence: $T(n) = 2T(n/2) + O(n)$ (similar to merge sort, yielding $O(n \log n)$)

Worst Case Recurrence: $T(n) = T(n-1) + O(n)$ (occurs when the pivot consistently partitions the array into one empty subproblem and one of size $n-1$, yielding $O(n^2)$).

Counting Binary Strings without Consecutive 1s

Consider counting binary strings of length $n$ that do not contain consecutive 1s. Let $a_n$ be the number of such strings. A string of length $n$ can end in either '0' or '1'.

• If a string ends in '0', the preceding $n-1$ characters can be any binary string of length $n-1$ without consecutive 1s. There are $a_{n-1}$ such strings.
• If a string ends in '1', the preceding character must be '0' to avoid consecutive 1s. So, the first $n-2$ characters must form a binary string of length $n-2$ without consecutive 1s, followed by '01'. There are $a_{n-2}$ such strings.

This gives the recurrence relation: $a_n = a_{n-1} + a_{n-2}$ for $n \ge 2$.

The initial conditions depend on how we define the start. If we consider strings of length 0, $a_0=1$ (empty string). For length 1, $a_1=2$ ("0", "1"). For length 2, $a_2=3$ ("00", "01", "10"). If we use $a_0=1, a_1=2$, the sequence starts 1, 2, 3, 5, 8, ... which relates to Fibonacci numbers shifted.

Catalan Numbers

Catalan numbers appear in many combinatorial problems, such as counting the number of valid sequences of parentheses, the number of binary trees with $n$ nodes, and the number of ways to triangulate a polygon. The recurrence relation for Catalan numbers $C_n$ is:

$C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$ for $n \ge 1$

With the initial condition $C_0 = 1$. The sequence begins: 1, 1, 2, 5, 14, 42, ...

The closed-form expression for Catalan numbers is $C_n = \frac{1}{n+1} \binom{2n}{n}$.

Solving Specific Discrete Math Recurrence Relations Examples

Let's walk through solving a few examples to illustrate the methods discussed.

Solving a Linear Homogeneous Recurrence Relation

Consider the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$ with initial conditions $a_0 = 1$ and $a_1 = 3$. This is a second-order linear homogeneous recurrence relation with constant coefficients.

Step 1: Form the characteristic equation.

The characteristic equation is $r^2 - 5r + 6 = 0$.

Step 2: Find the roots of the characteristic equation.

Factoring the quadratic equation, we get $(r-2)(r-3) = 0$. The roots are $r_1 = 2$ and $r_2 = 3$. Since the roots are distinct, the general solution is of the form $a_n = A_1 (2)^n + A_2 (3)^n$.

Step 3: Use the initial conditions to find the constants $A_1$ and $A_2$.

For $n=0$: $a_0 = A_1 (2)^0 + A_2 (3)^0 = A_1 + A_2 = 1$.

For $n=1$: $a_1 = A_1 (2)^1 + A_2 (3)^1 = 2A_1 + 3A_2 = 3$.

We have a system of two linear equations:

• $A_1 + A_2 = 1$
• $2A_1 + 3A_2 = 3$

From the first equation, $A_1 = 1 - A_2$. Substituting this into the second equation:

$2(1 - A_2) + 3A_2 = 3$

$2 - 2A_2 + 3A_2 = 3$

$A_2 = 1$.

Substituting $A_2 = 1$ back into $A_1 = 1 - A_2$, we get $A_1 = 1 - 1 = 0$.

Step 4: Write the closed-form solution.

With $A_1 = 0$ and $A_2 = 1$, the closed-form solution is $a_n = 0 \cdot (2)^n + 1 \cdot (3)^n = 3^n$.

Let's check: $a_0 = 3^0 = 1$, $a_1 = 3^1 = 3$, $a_2 = 3^2 = 9$. Using the recurrence: $a_2 = 5a_1 - 6a_0 = 5(3) - 6(1) = 15 - 6 = 9$. The solution is correct.

Solving a Linear Non-Homogeneous Recurrence Relation

Consider the recurrence relation $a_n = 2a_{n-1} + 1$ with initial condition $a_0 = 0$. This is a linear non-homogeneous recurrence relation.

Method 1: Iteration

• $a_0 = 0$
• $a_1 = 2a_0 + 1 = 2(0) + 1 = 1$
• $a_2 = 2a_1 + 1 = 2(1) + 1 = 3$
• $a_3 = 2a_2 + 1 = 2(3) + 1 = 7$
• $a_4 = 2a_3 + 1 = 2(7) + 1 = 15$

Observing the pattern: 0, 1, 3, 7, 15. It appears to be $2^n - 1$.

Let's verify by substituting:

$a_n = 2a_{n-1} + 1$

$a_n = 2(2a_{n-2} + 1) + 1 = 4a_{n-2} + 2 + 1$

$a_n = 4(2a_{n-3} + 1) + 2 + 1 = 8a_{n-3} + 4 + 2 + 1$

Continuing this pattern for $n$ steps, we get:

$a_n = 2^n a_0 + 2^{n-1} + 2^{n-2} + ... + 2^1 + 2^0$

Since $a_0 = 0$, this simplifies to the sum of a geometric series:

$a_n = 2^{n-1} + 2^{n-2} + ... + 2^1 + 1$

The sum of a geometric series $1 + r + r^2 + ... + r^{k-1}$ is $\frac{r^k - 1}{r - 1}$. Here, $r=2$ and the highest power is $n-1$, so there are $n$ terms from $2^0$ to $2^{n-1}$.

$a_n = \frac{2^n - 1}{2 - 1} = 2^n - 1$.

Method 2: Characteristic Equation for Non-Homogeneous Relations

For $a_n = 2a_{n-1} + 1$, the homogeneous part is $a_n = 2a_{n-1}$. The characteristic equation is $r - 2 = 0$, so $r = 2$. The homogeneous solution is $a_n^{(h)} = A \cdot 2^n$.

For the particular solution, since the non-homogeneous term is a constant ($1$), we guess a particular solution of the form $a_n^{(p)} = C$. Substituting into the recurrence relation:

$C = 2C + 1$

$-C = 1$, so $C = -1$.

The particular solution is $a_n^{(p)} = -1$.

The general solution is the sum of the homogeneous and particular solutions: $a_n = a_n^{(h)} + a_n^{(p)} = A \cdot 2^n - 1$.

Using the initial condition $a_0 = 0$:

$0 = A \cdot 2^0 - 1$

$0 = A - 1$, so $A = 1$.

The closed-form solution is $a_n = 1 \cdot 2^n - 1 = 2^n - 1$. This matches the result from the iteration method.

Solving a Recurrence Relation using Iteration

Let's consider $a_n = \frac{a_{n-1}}{2} + 1$ with $a_0 = 0$. We'll use the iteration method.

• $a_0 = 0$
• $a_1 = \frac{a_0}{2} + 1 = \frac{0}{2} + 1 = 1$
• $a_2 = \frac{a_1}{2} + 1 = \frac{1}{2} + 1 = \frac{3}{2}$
• $a_3 = \frac{a_2}{2} + 1 = \frac{3/2}{2} + 1 = \frac{3}{4} + 1 = \frac{7}{4}$
• $a_4 = \frac{a_3}{2} + 1 = \frac{7/4}{2} + 1 = \frac{7}{8} + 1 = \frac{15}{8}$

The pattern seems to be $a_n = \frac{2^n - 1}{2^{n-1}}$. Let's check this by rewriting $a_n$: $a_n = 2 - \frac{1}{2^{n-1}}$.

Let's substitute into the recurrence:

$a_n = \frac{a_{n-1}}{2} + 1$

$a_n = \frac{1}{2} \left( 2 - \frac{1}{2^{n-2}} \right) + 1$

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

$a_n = 2 - \frac{1}{2^{n-1}}$.

This confirms our pattern. The closed-form solution is $a_n = 2 - \frac{1}{2^{n-1}}$.

Applications of Recurrence Relations

The study of recurrence relations is far from purely theoretical; they are foundational for understanding and analyzing many real-world phenomena and computational processes. Their applications span various domains:

• Algorithm Analysis: As seen with binary search and merge sort, recurrence relations are essential for determining the time and space complexity of algorithms, especially those that use recursion.
• Computer Science Theory: They are used in analyzing data structures, graph algorithms, and formal languages.
• Combinatorics: Problems involving counting arrangements, permutations, combinations, and partitions are often modeled using recurrence relations (e.g., Catalan numbers, Fibonacci numbers).
• Economics and Finance: Modeling economic growth, interest accumulation, and financial derivatives can involve recurrence relations.
• Biology: Population growth models and the spread of diseases can be described using recurrence relations.
• Physics: Certain physical phenomena, such as oscillations and wave propagation, can be represented by difference equations.
• Computer Graphics: Fractals and recursive drawing algorithms often have underlying recurrence relations.

The ability to translate a problem into a recurrence relation and then solve it provides powerful insights into the problem's structure and behavior.

Conclusion

Mastering discrete math recurrence relations examples is a pivotal step in developing a robust understanding of discrete mathematics and its applications in computer science and beyond. We have explored what recurrence relations are, their various classifications, and the primary methods used for solving them, including the characteristic equation method, iteration, and generating functions. Through a variety of illustrative discrete math recurrence relations examples such as the Fibonacci sequence, Tower of Hanoi, and algorithmic complexity relations, we've demonstrated how these abstract concepts manifest in practical scenarios. By providing step-by-step solutions to specific examples, this article has aimed to equip you with the practical skills needed to identify, formulate, and solve recurrence relations. The pervasive nature of recurrence relations underscores their importance in analyzing processes that exhibit self-similarity or dependency on previous states.