Generating Functions Introduction

Math for CS · Axiom Academy

Encoding sequences as power series -- turning counting into algebra A generating function encodes a sequence of numbers as the coefficients of a power series. Instead of working with the sequence directly, we manipulate the series using algebraic operations. We treat these as formal power series -- we never plug in actual values of x . The variable x is just a bookkeeping device to keep track of which coefficient is which. Convergence doesn't matter. The power of generating functions comes from how algebraic operations correspond to combinatorial operations: Addition: A(x) + B(x) adds sequences term by term: c_n = a_n + b_n Multiplication: A(x) B(x) gives the convolution : c_n = _ k=0 ^ n a_k b_ n-k Shift: x A(x) shifts the sequence right by one position Differentiation: A'(x) multiplies each a_n by n and shifts left Generating functions turn recurrence relations into algebraic equations that can be solved for a closed form. From the recurrence: F(x) = x + xF(x) + x^2 F(x) Solve: F(x)(1 - x - x^2) = x , so F(x) = 1 - x - x^2 Use partial fractions to extract: F_n = [ ( 1+ 2 )^n - ( 1- 2 )^n ] This is Binet's formula -- a closed-form expression for the n -th Fibonacci number, derived purely through generating functions. Each coin type contributes a factor to the generating function: Pennies: 1 + x + x^2 + x^3 + = 1-x Nickels: 1 + x^5 + x^ 10 + = 1-x^5 Dimes: 1 + x^ 10 + x^ 20 + = 1-x^ 10

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