
- 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
Non-Homogeneous Recurrence Relations in Discrete Mathematics
Recurrence relations in discrete mathematics are quite useful in defining sequences based on previous terms. It allows us to predict future values or patterns. Up to this point, we may be familiar with homogeneous recurrence relations, where each term in a sequence depends only on its previous terms. Now we will cover the concept of non-homogeneous recurrence relations that introduce a new layer of complexity, since they add an extra function of n on the right-hand side of the relation.
In this chapter, we will see the fundamentals of non-homogeneous recurrence relations, methods for solving them, and an in-depth example for a better understanding.
What is a Non-Homogeneous Recurrence Relation?
In a non-homogeneous recurrence relation, we get an extra function of n. This is often denoted as f(n). In mathematical terms, the general form of a first-order non-homogeneous recurrence relation is −
$$\mathrm{a_n \:=\: c_1 \:\cdot\: a_{n-1} \:+\: f(n)}$$
In this case −
- an is the current term,
- an−1 is the previous term,
- c1 is a constant coefficient, and
- f(n) is a function of n. This is adding an additional layer of complexity.
If f(n) = 0, the relation is homogeneous. So, f(n) ≠ 0, the recurrence relation becomes non-homogeneous. This is because of this external function that we must consider. This extra component makes us solving non-homogeneous recurrence relations more complex than homogeneous ones because we need additional steps to obtain a closed-form solution.
Solving Non-Homogeneous Recurrence Relations
If we look closely, the process of solving non-homogeneous recurrence relations has two main steps:
- Solve the associated homogeneous recurrence relation − This step temporarily ignoring f(n) to find what is known as the homogeneous solution anh.
- Find the particular solution anp − Here, we account for f(n) by "guessing" the form of the solution and solving for unknown constants. By combining both solutions we got from the general solution.
These two steps might sound straightforward, but let us see through an example.
Step 1: Solving the Associated Homogeneous Recurrence Relation
For this step, we ignore f(n) in the recurrence relation and solve it as if it were homogeneous. This approach is called getting the associated homogeneous recurrence relation. Here, we use a similar techniques to those we have seen in homogeneous relations. We create the characteristic equation and solving for roots.
Take a look at the following Example −
Suppose we have a recurrence relation like −
$$\mathrm{a_n \:=\: 3a_{n-1} \:+\: 2n}$$
To find the homogeneous solution, we ignore the 2n term and instead solve −
$$\mathrm{a_n \:= \:3a_{n-1}}$$
From this, we form the characteristic equation −
$$\mathrm{r \:=\: 3}$$
This gives us a homogeneous solution of the form −
$$\mathrm{a_{nh} \:=\: A \:\cdot\: 3^n}$$
where A is an unknown constant to be determined later.
Step 2: Finding the Particular Solution anp
With the homogeneous solution in hand, we now need a particular solution that accounts for the 2n term in our recurrence relation. The form of the particular solution depends on the type of function f(n) is.
To guess anp based on f(n), in a correct way, we can follow a thumb rule.
- If f(n) is a constant, the guess for anp is also a constant.
- If f(n) is linear (like n), the guess should be linear: anp = Cn + D.
- If f(n) is quadratic (like n2), the guess would be quadratic: anp = Cn2 + Dn + E.
So using our example, since f(n) = 2n. This is linear, we set our particular solution as −
$$\mathrm{a_{np} \:=\: Cn \:+\: D}$$
Solving for C and D
To get the values of C and D, we substitute the value of anp = Cn + D back into the original recurrence relation −
$$\mathrm{a_n \:=\: 3a_{n-1} \:+\: 2n}$$
Replacing an with Cn + D and an−1 with C(n − 1) + D, we get −
$$\mathrm{Cn \:+\: D \:=\: 3\left(C(n \:-\: 1) \:+\: D\right) \:+\: 2n}$$
Now expanding and simplifying terms gives us the path to solve for C and D. It will get the result for particular solution.
Combining the Solutions
Once we have both the homogeneous solution anh and the particular solution anp, we can combine them to get the general solution:
$$\mathrm{a_n \:=\: a_{n h} \:+\: a_{np}}$$
In our example, this would give us a final solution that accounts for both the homogeneous and non-homogeneous components of the recurrence relation.
Real-world Applications of Non-Homogeneous Recurrence Relations
Non-homogeneous recurrence relations are used in many areas of mathematics and science. They extend the power of recurrence relations to handle real-world problems with added complexities. This helps us to model more dynamic systems and situations accurately.
Some applications of Non-homogeneous recurrence relations are given in the following list:
- Finance − Calculating compound interest with additional periodic payments.
- Physics − Modeling motion with an added constant force.
- Computer Science − Analyzing algorithm efficiency with constant additional steps at each recursion.
For instance, if we are calculating compound interest on a loan where additional fixed payments are made each period. Here the recurrence relation could include a constant f(n) to represent these fixed payments. Similarly, in algorithm analysis, a non-homogeneous recurrence could reflect a fixed cost of a certain operation in addition to recursive steps.
Conclusion
Non-homogeneous recurrence relations are characterized by an extra function f(n) in the formula that sets them apart from homogeneous relations. We explored a clear two-step process to solve them by first finding the associated homogeneous solution and then the particular solution.