Recurrence Relations

Math for CS · Axiom Academy

From algorithms to closed-form solutions What Is a Recurrence Relation? A recurrence relation defines a sequence where each term is expressed as a function of previous terms. In computer science, recurrences naturally arise when we analyze recursive algorithms. Our goal is always the same: start with the recursive definition, then find a closed-form expression that tells us T(n) directly without recursion. Every recursive algorithm has a recurrence hiding inside it. Consider merge sort : The algorithm makes 2 recursive calls , each on a subproblem of size n/2 , then does O(n) work to merge. This gives: Binary search: T(n) = T(n/2) + O(1) — one recursive call, constant work Karatsuba multiplication: — three subproblems A linear recurrence with constant coefficients has the form: where are constants. This is homogeneous if there is no extra additive term. Linear recurrences are the most tractable class — we have a systematic method to solve them. The Characteristic Equation Method For a homogeneous linear recurrence , we guess a solution of the form a_n = r^n and substitute: Dividing both sides by r^ n-k : If all k roots are distinct, the general solution is: where the constants are determined by the initial conditions. If a root r has multiplicity m , it contributes m terms: Let's solve F(n) = F(n-1) + F(n-2) with . Step 1: Write the characteristic equation: Step 2: Solve using the quadratic formula: Step 4: Use initial conditions to find A and B :

This is the written version of the interactive lesson above. See the full Math for CS course.