Solving Recurrence Examples

Combinatorics · Axiom Academy

EXAMPLE Solving Recurrence Examples Master recurrence relations through step-by-step worked examples Excellent work! You've completed multiple recurrence relation examples. Here's what we learned: Linear Homogeneous Recurrences: For relations like a_n = c_1a_ n-1 + c_2a_ n-2 , form the characteristic equation r^2 - c_1r - c_2 = 0 and find roots to get the general solution. Distinct vs. Repeated Roots: Distinct roots give a_n = A·r_1^n + B·r_2^n , while repeated roots give a_n = (A + Bn)r^n . Initial Conditions: Always use initial conditions to solve for constants in the general solution to get the specific closed form. Tower of Hanoi Pattern: Many divide-and-conquer algorithms follow the pattern T(n) = 2T(n-1) + 1 , which has the closed form T(n) = 2^n - 1 . Verification: After finding a closed form, verify it satisfies both the recurrence relation and the initial conditions. These techniques are fundamental for analyzing algorithms and solving counting problems. Practice identifying recurrence types and applying the appropriate solution method!

This is the written version of the interactive lesson above. See the full Combinatorics course.