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 −

• a_n is the current term,
• a_n−1 is the previous term,
• c₁ 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 a_nh.
• Find the particular solution a_np − 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 a_np

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 a_np based on f(n), in a correct way, we can follow a thumb rule.

• If f(n) is a constant, the guess for a_np is also a constant.
• If f(n) is linear (like n), the guess should be linear: a_np = C_n + D.
• If f(n) is quadratic (like n²), the guess would be quadratic: a_np = Cn² + 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 a_np = C_n + D back into the original recurrence relation −

$$\mathrm{a_n \:=\: 3a_{n-1} \:+\: 2n}$$

Replacing a_n with C_n + D and a_n−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 a_nh and the particular solution a_np, 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.