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(n²). 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 n². 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.