Undergraduate
  1. Algebra  1.1. Linear Algebra  1.1.1. Matrices  1.1.2. Determinants  1.1.3. Systems of Linear Equations  1.1.4. Vector Spaces  1.1.5. Linear Transformations  1.1.6. Eigenvalues and Eigenvectors  1.1.7. Diagonalization  1.1.8. Inner Product Spaces  1.1.9. Orthogonality and Orthonormal Bases  1.1.10. Singular Value Decomposition  1.2. Abstract Algebra  1.2.1. Groups  1.2.2. Subgroups  1.2.3. Cyclic Groups  1.2.4. Permutation Groups  1.2.5. Homomorphisms  1.2.6. Normal Subgroups  1.2.7. Rings  1.2.8. Fields  1.2.9. Ideals and Quotient Rings  1.2.10. Polynomial Rings  1.2.11. Vector Spaces over Fields  1.2.12. Modules  1.2.13. Galois Theory
  2. Calculus  2.1. Differential Calculus  2.1.1. Limits  2.1.2. Continuity  2.1.3. Derivatives  2.1.4. Chain Rule  2.1.5. Implicit Differentiation  2.1.6. Applications of Derivatives  2.1.7. Optimization Problems  2.1.8. Mean Value Theorem  2.2. Integral Calculus  2.2.1. Definite Integrals  2.2.2. Indefinite Integrals  2.2.3. Techniques of Integration  2.2.4. Improper Integrals  2.2.5. Applications of Integration  2.2.6. Arc Length and Surface Area  2.3. Multivariable Calculus  2.3.1. Partial Derivatives  2.3.2. Gradient  2.3.3. Divergence and Curl  2.3.4. Multiple Integrals  2.3.5. Line Integrals  2.3.6. Surface Integrals  2.3.7. Green's Theorem  2.3.8. Stokes' Theorem  2.3.9. Divergence Theorem  2.3.10. Jacobians
  3. Differential Equations  3.1. Ordinary Differential Equations  3.1.1. First Order Differential Equations  3.1.2. Higher Order Differential Equations  3.1.3. Systems of Differential Equations  3.1.4. Series Solutions  3.1.5. Numerical Methods for ODEs  3.2. Partial Differential Equations  3.2.1. Heat Equation  3.2.2. Wave Equation  3.2.3. Laplace Equation  3.2.4. Separation of Variables  3.2.5. Fourier Transform Methods
  4. Real Analysis  4.1. Sequences and Series  4.1.1. Convergence of Sequences  4.1.2. Series Tests  4.1.3. Power Series  4.1.4. Uniform Convergence  4.2. Functions of Real Variables  4.2.1. Limits and Continuity  4.2.2. Uniform Continuity  4.2.3. Differentiation in Functions of Real Variables  4.2.4. Riemann Integration  4.2.5. Lebesgue Integration
  5. Complex Analysis  5.1. Complex Numbers  5.1.1. Polar Form  5.1.2. Exponential Form  5.2. Functions of a Complex Variable  5.2.1. Analytic Functions  5.2.2. Cauchy-Riemann Equations  5.2.3. Contour Integrals  5.2.4. Cauchy's Integral Theorem  5.2.5. Residue Theorem  5.2.6. Conformal Mapping
  6. Probability and Statistics  6.1. Probability Theory  6.1.1. Basic Probability Concepts  6.1.2. Random Variables  6.1.3. Probability Distributions  6.1.4. Expectation and Variance  6.1.5. Conditional Probability and Bayes' Theorem  6.2. Statistics  6.2.1. Descriptive Statistics  6.2.2. Inferential Statistics  6.2.3. Hypothesis Testing  6.2.4. Regression Analysis  6.2.5. ANOVA
  7. Numerical Methods  7.1. Root-Finding Algorithms  7.2. Numerical Integration  7.3. Numerical Differentiation  7.4. Numerical Solutions to Differential Equations  7.5. Matrix Computations  7.6. Interpolation and Extrapolation
  8. Discrete Mathematics  8.1. Logic and Proof  8.2. Combinatorics  8.3. Graph Theory  8.4. Boolean Algebra  8.5. Recurrence Relations
  9. Linear Programming and Optimization  9.1. Simplex Method  9.2. Duality  9.3. Integer Programming  9.4. Nonlinear Optimization
  10. Topology  10.1. Metric Spaces  10.2. Topological Spaces  10.3. Continuity and Homeomorphisms  10.4. Compactness  10.5. Connectedness
  11. Geometry  11.1. Euclidean Geometry  11.2. Differential Geometry  11.3. Non-Euclidean Geometry  11.4. Projective Geometry
  12. Mathematical Physics  12.1. Fourier Series  12.2. Laplace Transforms  12.3. Applications of Differential Equations  12.4. Special Functions
  13. Set Theory and Logic  13.1. Sets and Subsets  13.2. Relations and Functions  13.3. Cardinality  13.4. Formal Logic  13.5. Zermelo-Fraenkel Set Theory
  14. Functional Analysis  14.1. Normed Spaces  14.2. Banach Spaces  14.3. Hilbert Spaces  14.4. Linear Operators

Undergraduate → Discrete Mathematics ↓


Recurrence Relations


Recurrence relation is an interesting and powerful concept in discrete mathematics that is widely used in computer science, especially in the analysis of algorithms and the calculation of series. The basic idea behind a recurrence relation is that it expresses a sequence of numbers (or other elements) in which each term is defined in terms of one or more of its previous terms.

Understanding recurrence relations involves tracing how the sequence evolves step-by-step and, if possible, finding a direct formula for the nth term, known as the closed-form solution. Let's look at these concepts step-by-step, exploring their properties, the different types, ways to solve them, and their applications, with numerous examples.

Basic concept

The recurrence relation for a sequence a n is an equation that expresses a n in terms of one or more of its predecessors, such as a n-1, a n-2, ..., etc., as well as some initial terms. The sequence is generated recursively, which means that after determining a certain number of initial terms, each subsequent term can be determined by applying the formula to earlier terms.

Formulating a recurrence relation

There are various forms of recurrence relations, and they can generally be divided according to their characteristics: order, linearity, and symmetry. The order of a recurrence relation refers to how many previous terms have been used. For example, a recurrence relation is of order k if a n is expressed as a n-1, a n-2, ..., a nk.

Examples of recurrence relations

Let's consider one of the most famous examples of a recurrence relation: the Fibonacci sequence. The sequence starts with the following initial conditions:

a 0 = 0
a 1 = 1

And each next term is the sum of the two terms preceding it:

a n = a n-1 + a n-2 where n ≥ 2

Another simple example is a sequence where each term is twice the previous term:

a 0 = 1
a n = 2 * a n - 1 where n ≥ 1

This sequence produces the following terms: 1, 2, 4, 8, 16, ..., and proceeds by multiplying each term by 2.

Classification of recurrence relations

Recurrence relations can be classified into different categories based on certain properties:

  • Linear vs. Nonlinear: A recurrence relation is said to be linear if each term a nk (for some constant k) is multiplied by a constant and no terms are multiplied together. Otherwise, it is nonlinear.
  • Homogeneous vs. Nonhomogeneous: A linear recurrence relation is homogeneous if none of the terms in it are constants (the terms depend on n but not on the sequence).
  • Order: The order of a recurrence relation is the number of previous terms to which it is related in defining each term of the sequence.

Classification examples

Consider the following examples:

a n = 3a n-1 + 4a n-2 (linear and homogeneous of order 2)
a n = 2a n - 1 + n (linear and non-uniform)
a n = a n-1 ^2 + a n-2 (non-linear)

Solution of recurrence relations

Solving a recurrence relation involves finding a function, usually expressed as n, that gives any term of the sequence directly without needing to know the previous terms. Here we describe some of the methods used to solve recurrence relations.

Replacement method

The substitution method, also called "iteration of repetitions", involves assuming a normal form and proving, through substitution and mathematical induction, that it is true for all n.

For the recurrence relation a n = 2a n-1 with the initial term a 0 = 1, we will consider a solution of the form:

a n = 2^n

By induction it can be verified that this form satisfies the recurrence relation and the initial condition.

Characteristic equation method

This method is mainly used for linear homogeneous recurrence relations. It involves writing the recurrence relation in the form of characteristic equations.

Consider the recurrence a n = 5a n-1 - 6a n-2. Assume a solution of the form a n = r^n Substitution gives the characteristic equation:

r^2 = 5r - 6

Solving this quadratic equation will provide the roots, allowing a general solution to be constructed based on these roots.

Generating function

Generating functions are useful for finding explicit formulas for recursively defined sequences. A generating function is a formal power series whose coefficients are the terms of the sequence.

For a given sequence {a n }, the generating function is given by:

g(x) = a 0 + a 1 x + a 2 x 2 + ...

By manipulating this series, we can often obtain a closed-form expression for an.

Applications of recurrence relations

Recurrence relations are used in a variety of fields and problems. They are commonly used in algorithm design and analysis, dynamic programming, financial modeling, and computer graphics. Here are some typical applications:

  • Algorithm analysis: Recurrence relations often reflect the time complexity of recursive algorithms. For example, the merge sort algorithm leads to the recurrence relation T(n) = 2T(n/2) + n.
  • Dynamic Programming: Many dynamic programming solutions are based on recurrence relations. Problems like Longest Common Subsequence, Knapsack problem, etc. are solved using recurrence relations.
  • Counting problems: Many counting problems use recurrence relations, such as counting the number of binary trees with n nodes. These can be derived recursively and then solved for closed-form solutions.

Explained examples with step by step solutions

Let's look at a detailed example to fully understand how recurrence relations are formulated and solved.

Example 1: Fibonacci sequence

We previously introduced the Fibonacci sequence, which is defined as:

a 0 = 0, a 1 = 1
a n = a n-1 + a n-2 where n ≥ 2

To solve this recurrence relation, assume a characteristic solution of the form a n = r^n Substituting, we get:

r^n = r^(n-1) + r^(n-2)


r^2 = r + 1

We use the quadratic formula to solve the characteristic equation:

r = (1 ± √5) / 2

Let's call these roots r1 and r2. The general solution to the Fibonacci recurrence is a combination of solutions for each root:

a n = c 1 r1^n + c 2 r2^n

Using the initial conditions, we determine the values 0, 1 of C 1 and C 2 for the standard sequence, thus arriving at the known closed form.

Example 2: Linear homogeneous recurrence

Given the relation a n = 3a n-1 - 4a n-2 with initial terms a 0 = 1, a 1 = 2, we solve by setting:

r^2 = 3r - 4

Solving, we get that r1 = 4, r2 = -1. Therefore, the general solution is:

a n = c 1 4^n + c 2 (-1)^n

Using the initial conditions, we find C 1 and C 2 to match a 0 = 1 and a 1 = 2, which generates the terms.

Conclusion

Recurrence relations are the backbone in the study of sequences and iterative algorithms. Understanding them allows one to model complex processes in a simple way and obtain solutions for recursive problems. As seen, they are versatile, with solutions available through various techniques such as substitution, characteristic equations, and generating functions, showing their power and relevance in various mathematical and real-world application contexts.


Undergraduate → 8.5


U
username
0%
completed in Undergraduate

← Prev (8.4)
Boolean Algebra
Next (9) →
Linear Programming and Optimization

Comments 



Recurrence Relations

https://www.buddymath.com/ug/8.5?bmal=en