🧩Discrete Mathematics Unit 13 – Recurrence Relations

What Are Recurrence Relations?

• Define sequences recursively by expressing later terms as a function of earlier terms
• Consist of an initial condition specifying the first term(s) and a recurrence relation defining $a_n$ in terms of preceding terms
• Useful for modeling problems involving recursion or reducing a problem to smaller subproblems
• Commonly arise in analysis of algorithms to determine time complexity
• Example recurrence relation: Fibonacci sequence where $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$

Types of Recurrence Relations

• Linear recurrence relations express $a_n$ as a linear combination of previous terms
  • Example: $a_n = 3a_{n-1} - 2a_{n-2}$ with $a_0 = 1$ and $a_1 = 2$
• Non-linear recurrence relations involve non-linear operations on previous terms
  • Example: $a_n = a_{n-1}^2 + a_{n-2}$ with $a_0 = 1$ and $a_1 = 2$
• Homogeneous recurrence relations have no additional terms beyond the linear combination of previous terms
• Non-homogeneous (inhomogeneous) recurrence relations include additional terms or functions
  • Example: $a_n = 2a_{n-1} + 3^n$ with $a_0 = 1$
• First-order recurrence relations depend only on the immediately preceding term $a_{n-1}$
• Higher-order recurrence relations depend on multiple preceding terms

Solving Linear Recurrence Relations

• Goal is to find a closed-form expression for the nth term $a_n$ without recursion
• Techniques for solving linear recurrence relations include iteration, characteristic equation method, and generating functions
• Iteration involves repeatedly applying the recurrence relation to express $a_n$ in terms of initial conditions
  • Example: Given $a_n = 2a_{n-1} - a_{n-2}$ with $a_0 = 1$ and $a_1 = 2$, iterate to express $a_2$, $a_3$, etc. in terms of $a_0$ and $a_1$
• Characteristic equation method converts the recurrence relation into a polynomial equation
  • Roots of the characteristic equation determine the form of the solution
• Generating functions transform the recurrence relation into an algebraic equation involving power series
  • Manipulate the equation and extract coefficients to obtain a closed-form solution

The Characteristic Equation Method

• Assume the solution has the form $a_n = r^n$ for some constant $r$
• Substitute $a_n = r^n$ into the recurrence relation and simplify
• Obtain the characteristic equation, a polynomial in $r$
  • Example: For $a_n = 3a_{n-1} - 2a_{n-2}$, the characteristic equation is $r^2 - 3r + 2 = 0$
• Find the roots of the characteristic equation
  • Distinct real roots lead to a solution of the form $a_n = c_1r_1^n + c_2r_2^n$
  • Repeated real roots lead to a solution of the form $a_n = (c_1 + c_2n)r^n$
  • Complex conjugate roots lead to a solution involving trigonometric functions
• Determine constants (e.g., $c_1$, $c_2$) using initial conditions

Generating Functions and Recurrences

• Define the generating function $A(x) = \sum_{n=0}^{\infty} a_nx^n$ for the sequence $\{a_n\}$
• Multiply the recurrence relation by $x^n$ and sum over all $n$ to obtain an equation involving $A(x)$
  • Example: For $a_n = 2a_{n-1} + 3^n$ with $a_0 = 1$, the equation is $A(x) = 1 + 2xA(x) + \frac{1}{1-3x}$
• Solve the equation for $A(x)$ using algebraic manipulations
• Decompose $A(x)$ into partial fractions or expand as a power series
• Extract the coefficient of $x^n$ to obtain a closed-form expression for $a_n$
  • Example: $A(x) = \frac{1}{1-2x} + \frac{1}{(1-2x)(1-3x)}$ leads to $a_n = 2^n + \frac{1}{2}(3^n - 2^n)$

Applications in Computer Science

• Analyze time complexity of recursive algorithms using recurrence relations
  • Example: Merge sort has the recurrence $T(n) = 2T(n/2) + O(n)$, solving gives $T(n) = O(n \log n)$
• Solve counting problems by setting up recurrence relations
  • Example: Count the number of binary strings of length $n$ without consecutive 1s
• Model dynamic programming algorithms using recurrence relations
  • Example: Bellman-Ford algorithm for shortest paths uses the recurrence $d_n(v) = \min\{d_{n-1}(v), \min_{(u,v) \in E}\{d_{n-1}(u) + w(u,v)\}\}$
• Describe growth of data structures or sequences in computer science problems
  • Example: Number of nodes in a complete binary tree of height $h$ satisfies $N(h) = 2N(h-1) + 1$ with $N(0) = 1$

Common Pitfalls and How to Avoid Them

• Forgetting to specify initial conditions or providing insufficient initial conditions
  • Always state the initial condition(s) along with the recurrence relation
• Incorrectly applying the characteristic equation method when roots are repeated or complex
  • Carefully consider the form of the solution based on the nature of the roots
• Mishandling summation indices or limits when manipulating generating functions
  • Pay attention to the range of summation and adjust indices as needed
• Attempting to solve non-linear recurrence relations using techniques for linear recurrences
  • Recognize the type of recurrence relation and apply appropriate solving techniques
• Overlooking the homogeneous or non-homogeneous nature of the recurrence relation
  • Identify whether additional terms are present and handle them accordingly

Practice Problems and Solutions

1. Solve the recurrence relation $a_n = 4a_{n-1} - 4a_{n-2}$ with $a_0 = 1$ and $a_1 = 2$.

   • Characteristic equation: $r^2 - 4r + 4 = 0$
   • Roots: $r = 2$ (repeated)
   • Solution: $a_n = (c_1 + c_2n)2^n$
   • Using initial conditions: $a_n = (1 + n)2^n$

2. Find a closed-form expression for the sequence defined by $a_n = 2a_{n-1} + 2^n$ with $a_0 = 1$ using generating functions.

   • Generating function equation: $A(x) = 1 + 2xA(x) + \frac{1}{1-2x}$
   • Solving for $A(x)$: $A(x) = \frac{1}{(1-2x)^2}$
   • Expanding as a power series: $A(x) = \sum_{n=0}^{\infty} (n+1)2^nx^n$
   • Closed-form expression: $a_n = (n+1)2^n$

3. Analyze the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$ arising from the analysis of the Karatsuba algorithm for integer multiplication.

   • Guess the solution: $T(n) = O(n^{\log_2 3})$
   • Prove by induction:
     • Base case: Holds for small $n$
     • Inductive step: Assume true for $m < n$, show true for $n$
   • Conclusion: $T(n) = O(n^{\log_2 3}) \approx O(n^{1.585})$, better than the $O(n^2)$ naive algorithm