
- 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
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 an is the current term, an−1 is the previous term, now c1 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 an 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 −
- a1 =2 × a0 = 2 × 2 =4
- a2 =2 × a1 = 2 × 4 =8
- a3 =2 × a2 = 2 × 8 =16
From these terms, we can identify a pattern: an = 2n
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 an in terms of a0.
Take a look at the following example −
$$\mathrm{a_n \:=\: 3 a_{n-1}, \quad a_0 \:=\: 5}$$
Start by rewriting as an in terms of previous terms:
- an = 3an−1 = 3(3an−2)
- Continuing, an = 3na0
Substitute a0 = 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 a0 (or any other starting term given), we can use the following formula to find the nth 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 − a0 = 5
Find the common ratio: − r = 3
Use the formula − an = 5 ⋅ 3n
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 a1 rather than a0.
Rewrite the formula using a1: an = a1 ⋅ rn−1
Substitute values: With r = 4, an = 7 ⋅ 4n−1
Verifying the Solution
Let us check it is fine or not. We can check that our formula works by calculating the first few terms −
- a1 = 7
- a2 = 7 ⋅ 4 = 28
- a3 = 7 ⋅ 42 = 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 An 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.