Solving Recurrences with OGFs

Combinatorics · Axiom Academy

LESSON Solving Recurrences with OGFs Learn how to transform recurrence relations into algebraic equations using ordinary generating functions, then solve for closed forms 1. Setting Up the OGF Equation Consider the Fibonacci recurrence: F n = F n-1 + F n-2 with initial conditions F 0 = 0, F 1 = 1. Step 1: Multiply the recurrence by x n : Step 2: Sum from n=2 to ∞ (where the recurrence is valid): Step 3: Express in terms of F(x): 2. Solving for F(x) Algebraically Once we have an equation in terms of F(x), we can solve for it using basic algebra. Now we have a rational function. The next step is to decompose it using partial fractions. 3. Partial Fraction Decomposition To extract the coefficient of x n , we decompose the rational function into simpler terms whose series expansions we know. Where φ is the golden ratio and ψ is its conjugate: Each partial fraction term has a known power series expansion. We use these to read off the coefficient of x n . Using the expansion 1/(1-ax) = Σ a n x n : Therefore, the coefficient of x n is:

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