Linear Recurrence Relations in Discrete Mathematics

---

---

Linear recurrence relations are major concept in discrete mathematics that provide a mathematical way to define sequences based on prior terms. We often get such relations when we need to predict the subsequent future values using the previous terms.

Read this chapter to learn the basics of first-order linear homogeneous recurrence relations, understand their properties, methods of solving them, and also learn their applications.

What are Linear Recurrence Relations?

A recurrence relation is nothing but a formula which defines each term in a sequence as a function of its preceding terms. The recurrence relation gives us a "rule" to find each term based on earlier terms in the sequence.

Linear homogeneous recurrence relations consist of several relations. They are −

• Linear, which means they do not involve powers or non-linear transformations of previous terms.
• Homogeneous, which means they lack a constant term or function on the right-hand side.

First-Order Linear Homogeneous Recurrence Relations

Let us talk about the first-order recurrence relation. They depends only on the immediate previous term. The general form for a first-order linear homogeneous recurrence relation is −

$$\mathrm{a_n \:=\: c_1 a_{n-1}}$$

where a_n is the current term, a_n−1 is the previous term, now c₁ is a constant coefficient. This type of relation simply indicates that each term in the sequence is a constant multiple of the one before it.

For example, consider a recurrence relation like −

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

Here, every term is double the preceding term. And it results an exponential pattern like 2, 4, 8, 16, and so on.

Solving First-Order Linear Homogeneous Recurrence Relations

To solve these recurrence relations, we have to find an explicit formula. Or sometimes, the closed-form solution, for a_n in terms of n. Let us understand the two common methods: iteration and back substitution.

Iteration Method

This is the simplest method. It involves generating terms of the sequence by repeatedly applying the recurrence relation. This method is used to observe a pattern. Which we can then generalize into a closed-form solution.

Example

For the recurrence relation −

$$\mathrm{a_n \:=\: 2 a_{n-1}, \quad a_0 \:=\: 2}$$

Start by generating terms −

• a₁ =2 × a₀ = 2 × 2 =4
• a₂ =2 × a₁ = 2 × 4 =8
• a₃ =2 × a₂ = 2 × 8 =16

From these terms, we can identify a pattern: a_n = 2ⁿ

Thus, our closed-form solution is −

$$\mathrm{a_n \:=\: 2n}$$

Back Substitution Method

The back substitution method involves substituting terms into the recurrence relation, to rewrite a_n in terms of a₀.

Take a look at the following example −

$$\mathrm{a_n \:=\: 3 a_{n-1}, \quad a_0 \:=\: 5}$$

Start by rewriting as a_n in terms of previous terms:

• a_n = 3a_n−1 = 3(3a_n−2)
• Continuing, a_n = 3ⁿa₀

Substitute a₀ = 5 −

$$\mathrm{a_n \:=\: 3^n \:\cdot\: 5}$$

Our closed-form solution is −

$$\mathrm{a_n \:=\: 5 \:\cdot\: 3^n}$$

Geometric Progression and Common Ratios

For geometric progression too, we can use first-order linear homogeneous recurrence relations. In a geometric progression, each term is obtained by multiplying the previous term by a constant ratio r. In our examples, the constant ratio is the coefficient in the recurrence relation.

To find the common ratio r, we can divide a term by its preceding term −

$$\mathrm{r \:=\: \frac{a_n}{a_{n-1}}}$$

For example, in the sequence 2, 4, 8, 16, and so on, dividing the each term by the previous term will give a ratio of 2.

Applying Recurrence Relations to Find Explicit Formulas

If we have the common ratio r and the initial term a₀ (or any other starting term given), we can use the following formula to find the n^th term in the sequence −

$$\mathrm{a_n \:=\: a_0 \:\cdot\: r^n}$$

This formula is useful for quickly calculating terms without iterating through each step. Let us see a few more examples for a better understanding.

Example 1: Sequence with Ratio 3

Consider the sequence 5, 15, 45, 135, etc.

Identify the initial term − a₀ = 5

Find the common ratio: − r = 3

Use the formula − a_n = 5 ⋅ 3ⁿ

So, the closed-form solution is −

$$\mathrm{a_n \:=\: 5 \:\cdot\: 3^n}$$

Example 2: Different Starting Point

Suppose we have a sequence defined by −

$$\mathrm{a_n \:=\: 4 a_{n-1}, \quad a_1 \:=\: 7}$$

Identify the starting term a₁ rather than a₀.

Rewrite the formula using a₁: a_n = a₁ ⋅ rⁿ⁻¹

Substitute values: With r = 4, a_n = 7 ⋅ 4ⁿ⁻¹

Verifying the Solution

Let us check it is fine or not. We can check that our formula works by calculating the first few terms −

• a₁ = 7
• a₂ = 7 ⋅ 4 = 28
• a₃ = 7 ⋅ 4² = 112

The solution is correct.

First-Order Linear Homogeneous Recurrence Relations in Practice

In practice, the first-order recurrence relations are used in computer science for algorithms analysis. There we need repeating calculations. Generating Fibonacci numbers or performing binary search operations. The simplicity of this form gives relations highly efficient to solve. They also allow programmers to find future terms without computing each previous term individually.

Example: Compound Interest Calculation

An interesting example could be "compound interest", when compounded annually. We can model them as a recurrence relation.

Suppose we have an initial deposit P and an annual interest rate r. The amount A_n after n years can be given by −

$$\mathrm{A_n \:=\: (1 \:+\: r) A_{n-1}}$$

So for an initial deposit of Rs 1000 with an interest rate of 5%, the sequence would be −

$$\mathrm{A_n \:=\: 1000 \:\cdot\: (1.05)^n}$$

So that, after n years, the formula can tell the balance without calculating each year individually.

General Observations

We discussed first-order linear homogeneous recurrence relations; there are nonhomogeneous recurrence relations and higher-order recurrence relations too.

For non-homogeneous relations, an additional term is included that introduces new behavior into the sequence. It makes oscillations or exponential growth. Higher-order relations depend on more than one preceding term.

Conclusion

In this chapter, we covered the basics of first-order linear homogeneous recurrence relations, understood their structure, and demonstrated how to solve them through iteration and back substitution. We then applied these methods to real-world problems and simple sequences. We showed how recurrence relations allow us to predict terms in a sequence quickly.

In addition, we touched upon geometric progressions, which are integral to identifying patterns within recurrence relations. In the next chapter, we will see higher-order and non-homogeneous recurrence relations in action.