Recurrence Relation Definition

Recurrences, or recurrence relations, are equations that define sequences of values using recursion and initial values. Recurrences can be linear or non-linear, homogeneous or non-homogeneous, and first order or higher order.

For example,

For this sequence, the rule is add three.

Each number in a sequence is called a term and is identified by its position within the sequence. We write them as follows:

• The first term \(T(1) = 3\)
• The second term \(T(2) = 6\)
• The third term \(T(3) = 9\)
• The fourth term \(T(4) = 12\)
• The nth term \(T(n)\)

To generate this sequence we can use the nnth term formula for the sequence. For this sequence, the \(n\)th term would be \(T(n) = 3n\).

When \(n = 1\), \(T(1) = 3(1) = 3\).

When \(n = 2\), \(T(2) = 3(2) = 6\), and so on.

Another way of generating this sequence would be to use the recurrence relation, where each term is generated using the previous value. These recurrence relations are algorithms and can generate any term in the sequence.

When \(n = 1\), \(T(1) = 3\).

When \(n = 2\), \(T(2) = 3 + 3 = 6\).

When \(n = 3\), \(T(3) = 6 + 3 = 9\), and so on.

Hence, the recurrence equation can be written as the formula:

The initial value, \(T(1)\), would need to be provided. The initial value could also be \(T(0)\).

A recurrence relation for a sequence \(T(1), T(2), ..., T(n)\) is a formula that calculates each term \(T(k)\) in terms of \(T(k-1), T(k-2), ..., T(k-i)\) for some integer \(i\). The initial conditions for a recurrence relation specify values for \(T(1), T(2), ..., T(k-1)\).

Classifying Recurrence Relations

Recurrence relations are often classified based on how the terms are combined, the nature of their coefficients, and the number and nature of the previous terms involved. Below is a breakdown of the key classifications for recurrence relations:

1. By the Number of Previous Terms Used

1.1. First-Order Recurrence Relations

In first-order recurrence relations, only the immediately previous term is used to compute the next term. These relations are the simplest type and are often easy to solve.

Example 1: First-Order Constant-Coefficient Linear Homogeneous Recurrence

In this example, the next term is twice the previous term.

Example 2: First-Order Constant-Coefficient Linear Non-Homogeneous Recurrence

In this example, the next term depends on the previous term plus an additional term \(n\).

1.2. Second-Order Recurrence Relations

In second-order recurrence relations, the next term depends on the two previous terms. These relations are more complex than first-order ones, and the solution method is different (e.g., using the characteristic equation).

Example 1: Second-Order Constant-Coefficient Linear Homogeneous Recurrence

In this example, the next term is calculated based on a linear combination of the two previous terms.

Example 2: Second-Order Constant-Coefficient Linear Non-Homogeneous Recurrence

In this example, the next term is calculated based on a linear combination of the two previous terms plus an additional term (a constant value).

1.3. Higher-Order Recurrence Relations

In higher-order recurrence relations, the next term depends on three or more previous terms. These relations are even more complex and often require advanced techniques (such as matrix methods or generating functions) for solving.

Example 1: Higher-Order Constant-Coefficient Linear Homogeneous Recurrence

In this example, the next term is calculated based on a linear combination of the three previous terms.

Example 2: Higher-Order Constant-Coefficient Linear Non-Homogeneous Recurrence

In this example, the next term depends on a combination of the previous three terms and a quadratic function of \(n\).

2. By the Nature of the Coefficients

2.1. Constant-Coefficient Recurrence Relations

In Constant-Coefficient Recurrence Relations, the coefficients multiplying the previous terms are constant (i.e., they do not depend on nn). This is the most common type of recurrence relation and is often easier to solve.

Example 1: First-Order Constant-Coefficient Linear Homogeneous Recurrence

In this example, the next term depends on a linear combination of the previous term with constant coefficients.

Example 2: Second-Order Constant-Coefficient Linear Non-Homogeneous Recurrence

In this example, the next term depends on a linear combination of the previous terms with constant coefficients, and an additional unit (such as a constant value) is added at each step.

2.2. Variable-Coefficient Recurrence Relations

In Variable-Coefficient Recurrence Relations, the coefficients multiplying the previous terms are functions of \(n\) (i.e., they change as \(n\) increases). These are generally more complex than constant-coefficient recurrences.

Example 1: First-Order Variable-Coefficient Linear Homogeneous Recurrence

In this example, the next term depends on the previous term with variable coefficient.

Example 2: Second-Order Variable-Coefficient Linear Non-Homogeneous Recurrence

In this example, the next term depends on the previous terms with variable coefficients, and an additional unit (such as a constant value) is added at each step.

3. By the Combination of Terms

3.1. Linear Recurrence Relations

In linear recurrence relations, a sequence is defined using linear combinations of its previous terms.

Example 1: First-Order Constant-Coefficient Linear Homogeneous Recurrence

In this example, the next term depends on a linear combination of the two previous terms with constant coefficients.

3.1. Nonlinear Recurrence Relations

In nonlinear recurrence relations, a sequence is defined based on one or more previous terms, using a nonlinear operations (e.g., squaring, multiplying, taking powers, etc.).

Example 1: First-Order Constant-Coefficient Nonlinear Non-Homogeneous Recurrence

In this example, the next term depends on the non-linear previous term which is squared and a additional term.

4. By the Presence of additional terms

4.1. Homogeneous Recurrence Relations

In homogeneous recurrence relations, a sequence is defined based on its previous terms, and it relies solely on the values of those terms without any additional independent term.

Example 1: First-Order Constant-Coefficient Linear Homogeneous Recurrence

In this example, the next term depends on a linear combination of the two previous terms with constant coefficients and there are no additional independent terms.

4.2. Non-Homogeneous Recurrence Relations

In non-homogeneous recurrence relations, a sequence is defined based on its previous terms, and it includes additional independent terms.

Example 1: First-Order Constant-Coefficient Linear Non-Homogeneous Recurrence

In this example, the next term depends on a linear combination of the two previous terms with constant coefficients plus the additional independent term.