Key Concepts of Recurrence Relations to Know for Discrete Mathematics

Recurrence relations are key in understanding sequences where each term relies on previous ones. They connect to various mathematical concepts, like the Fibonacci sequence and combinatorial structures, making them essential in algebraic and enumerative combinatorics.

1. Linear recurrence relations

   • A linear recurrence relation defines a sequence where each term is a linear combination of previous terms.
   • It can be expressed in the form ( a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k} ).
   • The order of the relation is determined by the number of previous terms used.

2. Fibonacci sequence

   • The Fibonacci sequence is defined by the recurrence relation ( F_n = F_{n-1} + F_{n-2} ) with initial conditions ( F_0 = 0 ) and ( F_1 = 1 ).
   • It appears in various natural phenomena, such as the arrangement of leaves and the branching of trees.
   • The closed-form expression, known as Binet's formula, provides a direct way to compute Fibonacci numbers.

3. Arithmetic sequences

   • An arithmetic sequence is defined by a constant difference between consecutive terms, expressed as ( a_n = a_1 + (n-1)d ).
   • The first term is ( a_1 ) and ( d ) is the common difference.
   • The sum of the first ( n ) terms can be calculated using the formula ( S_n = \frac{n}{2} (2a_1 + (n-1)d) ).

4. Geometric sequences

   • A geometric sequence is defined by a constant ratio between consecutive terms, expressed as ( a_n = a_1 r^{n-1} ).
   • The first term is ( a_1 ) and ( r ) is the common ratio.
   • The sum of the first ( n ) terms can be calculated using the formula ( S_n = a_1 \frac{1 - r^n}{1 - r} ) for ( r \neq 1 ).

5. Homogeneous recurrence relations

   • A homogeneous recurrence relation has no additional terms or constants, expressed as ( a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k} ).
   • The solution typically involves finding the characteristic polynomial and its roots.
   • The general solution is a linear combination of the terms derived from the roots.

6. Non-homogeneous recurrence relations

   • A non-homogeneous recurrence relation includes additional terms, expressed as ( a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k} + f(n) ).
   • The solution consists of the homogeneous solution plus a particular solution to the non-homogeneous part.
   • Techniques for finding particular solutions include the method of undetermined coefficients and variation of parameters.

7. Characteristic equation method

   • The characteristic equation is derived from a homogeneous linear recurrence relation by substituting ( a_n = r^n ).
   • Solving the characteristic polynomial provides the roots, which determine the form of the general solution.
   • The nature of the roots (real, complex, repeated) affects the solution structure.

8. Generating functions for solving recurrences

   • A generating function is a formal power series that encodes a sequence, typically expressed as ( G(x) = a_0 + a_1 x + a_2 x^2 + \ldots ).
   • It transforms recurrence relations into algebraic equations, making them easier to solve.
   • The coefficients of the expanded series correspond to the terms of the original sequence.

9. Divide-and-conquer recurrences

   • Divide-and-conquer recurrences arise in algorithms that break a problem into smaller subproblems, such as ( T(n) = aT(n/b) + f(n) ).
   • They often describe the time complexity of recursive algorithms.
   • Analyzing these recurrences helps determine the overall efficiency of the algorithm.

10. Master theorem

    • The Master theorem provides a method for analyzing the time complexity of divide-and-conquer recurrences.
    • It offers a set of cases to determine the asymptotic behavior of ( T(n) ) based on the relationship between ( f(n) ) and ( n^{\log_b a} ).
    • It simplifies the process of solving many common recurrence relations without needing to derive them explicitly.

11. Catalan numbers

    • Catalan numbers count various combinatorial structures, such as valid parentheses combinations and binary search trees.
    • They can be defined by the recurrence relation ( C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i} ) with ( C_0 = 1 ).
    • The closed-form expression is given by ( C_n = \frac{1}{n+1} \binom{2n}{n} ).

12. Binomial coefficients recurrence

    • The binomial coefficients satisfy the recurrence relation ( \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} ).
    • This relation reflects the combinatorial interpretation of choosing ( k ) elements from ( n ).
    • The base cases are ( \binom{n}{0} = 1 ) and ( \binom{n}{n} = 1 ).

13. Stirling numbers recurrence

    • Stirling numbers of the second kind, denoted ( S(n, k) ), count the ways to partition ( n ) objects into ( k ) non-empty subsets.
    • They satisfy the recurrence relation ( S(n, k) = k S(n-1, k) + S(n-1, k-1) ).
    • The base cases are ( S(0, 0) = 1 ) and ( S(n, 0) = 0 ) for ( n > 0 ).

14. Tower of Hanoi recurrence

    • The Tower of Hanoi problem involves moving ( n ) disks from one peg to another, following specific rules.
    • The recurrence relation is ( T(n) = 2T(n-1) + 1 ) with base case ( T(1) = 1 ).
    • The solution is ( T(n) = 2^n - 1 ), representing the minimum number of moves required.

15. Solving recurrences using iteration

    • Iteration involves expanding the recurrence relation step-by-step to identify a pattern or closed form.
    • This method can reveal the relationship between terms and help derive a general formula.
    • It is particularly useful for simple recurrences where direct computation is feasible.