
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Solving Recurrence Relations in Discrete Mathematics
From algorithm analysis to sequence problems, recurrence relations are quite useful in discrete mathematics. Recurrence relations give us a way to express terms in a sequence based on prior terms.
In this chapter, we will explain the different ways of solving recurrence relations, focusing on using the iteration method. We will also go through an example to understand each step and highlight how we can determine the running time of recursive algorithms by finding a closed-form solution.
What is a Recurrence Relation?
Let's do a brief recap. A recurrence relation is an equation that expresses each term in a sequence in terms of its preceding terms. It is described how each element in a sequence can be calculated from the previous ones. We are essentially setting up a recursive process. In other words, if we know the initial terms and the rule behind the relation, we can compute each term in the sequence.
The general form for a recurrence relation is −
$$\mathrm{T(n) \:=\: T(n \:-\: 1) \:+\: f(n)}$$
where −
- T(n) is the term we are trying to find ,
- T(n − 1) is the previous term,
- f(n) represents any additional function of n that adds complexity, (non-homogeneous case)
When solving the recurrence relations, we focus on to find a closed-form solution. They are nothing but explicit formula for T(n) that does not require calculating all prior terms.
Types of Recurrence Relations
Let us recap for the types of recurrence relations to understand the concept better:
- Homogeneous Recurrence Relations − These have terms dependent only on previous terms, with no additional function.
- Non-Homogeneous Recurrence Relations − These have a function added to the recurrence, making them more complex to solve.
Using Iteration to Solve Recurrence Relations
To solve recurrence we must follow a set of rules. The very first rule is the iteration method. It is a systematic way to unfold the recurrence relation step-by-step.
By substituting terms progressively, we can identify and find a pattern. This is used for making it possible to generalize this pattern into a closed-form solution.
Step-by-Step Example of Iteration Method
Let us say we have the recurrence relation −
$$\mathrm{T(n) \:=\: T(n \:-\: 1) \:+\: 2n}$$
With a base case T(0) = 0. Our goal is to solve for T(n) using the iteration method.
Step 1: Set Up Columns for Iteration
In the iteration method, it can be useful to make a table with two columns to keep track of:
- The iteration step k,
- The function T(n) as we compute it at each step.
Step 2: Substitute Terms for Each Iteration
Iteration 1 − Start by expanding T(n) in terms of the previous steps.
$$\mathrm{T(n) \:=\: T(n \:-\: 1) \:+\: 2n}$$
Iteration 2 − To solve for T(n − 1), substitute again:
$$\mathrm{T(n \:-\: 1) \:=\: T(n \:-\: 2) \:+\: 2(n \:-\: 1)}$$
Now, substitute this result back into
$$\mathrm{T(n) \:=\: T(n \:-\: 2) \:+\: 2(n \:-\: 1) \:+\: 2n}$$
Iteration 3 − Similarly, substitute for T(n − 2):
$$\mathrm{T(n \:-\: 2) \:=\: T(n \:-\: 3) \:+\: 2(n \:-\: 2)}$$
Plugging back, we get −
$$\mathrm{T(n) \:=\: T(n \:-\: 3) \:+\: 2(n \:-\: 2) \:+\: 2(n \:-\: 1) \:+\: 2n}$$
Step 3: Look for a Pattern
We have seen the previous states. There is a pattern which starts to appear. By continuing the iterations, we find that each expansion adds a new term of 2 × some integer. This is multiplied by values from n, (n − 1), (n − 2) and so on.
Step 4: Derive the General Form
At each iteration k, the recurrence relation expands as follows −
$$\mathrm{T(n) \:=\: T(n \:-\:k) \:+\: \sum_{i=0}^{k-1} 2(n \:-\: i)}$$
Eventually, when k = n (since the base case T(0) = 0), we may have −
$$\mathrm{T(0) \:=\: 0 \:+\: \sum_{i=0}^{n-1} 2(n \:-\: i)}$$
Step 5: Simplify the Summation
Our equation now includes a summation as follows −
$$\mathrm{T(n)\:=\:\sum_{i=0}^{n-1}\:2(n\:-\:i)}$$
Simplify this by distributing and summing −
$$\mathrm{T(n)\:=\:2\sum_{i=0}^{n-1}\:(n-i) \:=\:2(n\:+\:(n\:-\:1)\:+\:(n\:-\:2)\:+\:\dotso\:+\:1)}$$
This is an arithmetic series, and it sums up to −
$$\mathrm{T(n) \:=\: 2\: \cdot\: \frac{n(n \:+\: 1)}{2} \:=\: n(n \:+\: 1)}$$
Final Closed Form and Interpretation
Thus, the closed-form solution for our recurrence relation is −
$$\mathrm{T(n) \:=\: n(n \:+\: 1)}$$
This solution is in Big-O notation as O(n2). This is indicating that the growth rate of T(n) is quadratic.
Understanding the Result
We have got the result T(n) = n(n + 1). This result shows that this recurrence relation grows at a rate proportional to n2. This is quite correct because each term in the sequence has adding a new increment. This scales up as n increases.
Example Applications
We get to see recurrence relations in algorithmic time complexity analysis. For instance, if an algorithm's runtime for an input of size n depends linearly on each previous step plus some increasing factor, the quadratic growth rate T(n) = n(n + 1) may describe the total running time.
Tips for Solving Recurrence Relations
While solving recurrence relations, we must follow some thumb rules −
- Look for Patterns Early − By tracking each of the substitution, we can sometimes see a pattern after only a few iterations.
- Use Known Summation Formulas − Understand the common summations like arithmetic or geometric series can save a lot of time.
- Do not forget the Base Case − Always find the base case when determining the final form of the solution.
- Verify − Substitute the closed-form solution back into the original recurrence to make it working.
Conclusion
In this chapter, we explained the process of solving recurrence relations in discrete mathematics. Focussing on the iteration method, we walked through each step, from setting up our terms to finding a general form, and finally deriving the closed-form solution. We also looked at how to interpret these results and apply them to real-world problems. With these techniques, we can solve various types of recurrence relations in practice.