6.4 Recurrence Relations

Recurrence relations are equations that define sequences by relating each term to previous ones. They're crucial in combinatorics and discrete math, helping model everything from population growth to algorithm complexity.

Solving these relations involves finding general solutions and applying initial conditions. This process unlocks powerful tools for analyzing patterns in discrete systems, connecting mathematical theory to real-world applications in computer science, finance, and beyond.

Recurrence relations: Definition and recognition

Definition and types of recurrence relations

• A recurrence relation is an equation that recursively defines a sequence, where the next term is a function of the previous terms
• Recurrence relations can be linear or non-linear, depending on whether the recurrence is a linear combination of previous terms
• Linear recurrence relations have terms that are multiplied by constants and added together
• Non-linear recurrence relations involve terms with exponents, products, or other non-linear functions

Applications and examples of recurrence relations

• Recurrence relations are commonly used to model population growth, financial problems, and algorithms in computer science
• The Fibonacci sequence is a well-known example of a recurrence relation, where each term is the sum of the two preceding terms
  • The Fibonacci sequence starts with 0 and 1, and each subsequent term is the sum of the previous two terms: 0, 1, 1, 2, 3, 5, 8, 13, ...
• The Tower of Hanoi puzzle can be modeled using a recurrence relation to determine the minimum number of moves required to solve the puzzle
  • The recurrence relation for the Tower of Hanoi is $T(n) = 2T(n-1) + 1$, where $T(n)$ is the number of moves required for $n$ disks

Solving homogeneous linear recurrence relations

Characteristic equation and roots

• A homogeneous linear recurrence relation with constant coefficients is a recurrence relation where the coefficients of the terms are constants and the right-hand side is zero
• The characteristic equation of a homogeneous linear recurrence relation is obtained by replacing each term with a power of a variable and setting the equation equal to zero
• The roots of the characteristic equation, called the characteristic roots, determine the form of the general solution to the recurrence relation
• If the characteristic equation has distinct roots, the general solution is a linear combination of terms involving the powers of the roots
• If the characteristic equation has repeated roots, the general solution includes additional terms with powers of n multiplied by the powers of the repeated roots

Determining the general solution and specific solution

• The general solution to a homogeneous linear recurrence relation is a linear combination of the terms determined by the characteristic roots
• For distinct roots $r_1, r_2, ..., r_k$, the general solution is of the form $[a_n](https://www.fiveableKeyTerm:a_n) = c_1r_1^n + c_2r_2^n + ... + c_kr_k^n$, where $c_1, c_2, ..., c_k$ are constants
• For a repeated root $r$ with multiplicity $m$, the general solution includes terms of the form $c_1r^n + c_2nr^n + ... + c_mn^{m-1}r^n$
• The initial conditions of the recurrence relation are used to determine the specific values of the constants in the general solution
• Substitute the initial conditions into the general solution and solve the resulting system of equations to find the values of the constants

Finding particular solutions for non-homogeneous relations

Method of undetermined coefficients

• A non-homogeneous linear recurrence relation has a non-zero function on the right-hand side of the equation
• The general solution to a non-homogeneous linear recurrence relation is the sum of the homogeneous solution and a particular solution
• The method of undetermined coefficients is used to find a particular solution by assuming a specific form based on the right-hand side function
• If the right-hand side is a polynomial, the particular solution will be a polynomial of the same degree with undetermined coefficients
• If the right-hand side is an exponential function, the particular solution will be an exponential function with the same base and undetermined coefficients
• If the right-hand side is a combination of polynomials and exponential functions, the particular solution will be a combination of the corresponding forms

Solving for the particular solution

• To find the particular solution, assume a form for the solution based on the right-hand side function
• Substitute the assumed particular solution into the recurrence relation
• Equate the coefficients of like terms on both sides of the equation to obtain a system of equations for the undetermined coefficients
• Solve the system of equations to determine the values of the undetermined coefficients
• The particular solution is the assumed form with the determined values of the coefficients

Applications of recurrence relations in computer science

Analysis of algorithms

• Recurrence relations are used to analyze the time complexity of recursive algorithms in computer science
• The recurrence relation for an algorithm expresses the running time of the algorithm in terms of the running time of smaller subproblems
• The Master Theorem is a method for solving recurrence relations that arise in the analysis of divide-and-conquer algorithms
  • The Master Theorem provides a formula for the solution of recurrences of the form $T(n) = aT(n/b) + f(n)$, where $a \geq 1$, $b > 1$, and $f(n)$ is a given function

Other applications

• Recurrence relations can model the growth of populations over time, such as bacterial growth or the spread of a virus
  • The logistic growth model uses a recurrence relation to describe the growth of a population with limited resources
• In finance, recurrence relations can model compound interest, annuities, and amortization schedules
  • The compound interest formula $A = P(1 + r)^n$ can be expressed as a recurrence relation: $A_n = (1 + r)A_{n-1}$
• Recurrence relations are used in the study of dynamical systems to model the evolution of a system over time
  • The logistic map is a recurrence relation that models population growth with a carrying capacity
• In combinatorics, recurrence relations can be used to count the number of ways to arrange objects or solve problems involving sequences
  • The Catalan numbers, which count the number of valid parentheses expressions, can be defined by the recurrence relation $C_n = \sum_{i=0}^{n-1} C_iC_{n-1-i}$