Polynomial multiplication, Fibonacci, and coin counting
A generating function encodes a sequence a₀, a₁, a₂, ... as the coefficients of a formal power series: f(x) = a₀ + a₁x + a₂x² + ... This algebraic trick transforms counting problems into polynomial (or series) arithmetic. Multiplication of generating functions corresponds to convolution of sequences.
In this lesson, you will see how polynomial multiplication implements convolution, derive the Fibonacci closed form via generating functions, and solve a coin-change problem using products of geometric series.
When you multiply two polynomials, each coefficient of the result is a sum of products: cₖ = Σ aᵢ · bₖ₋ᵢ. This is exactly convolution. Click a result coefficient to see which pairs of input coefficients contribute to it.
Polynomial multiplication is convolution: c_k = Σ a_i · b_(k-i). Click an index to see contributing pairs.
Key insight: Convolution is the algebraic engine behind generating functions. Many counting problems reduce to multiplying generating functions and reading off coefficients.
The Fibonacci recurrence fₙ = fₙ₋₁ + fₙ₋₂ translates into an algebraic equation for the generating function F(x). Solving it and decomposing into partial fractions yields Binet's formula: an exact closed form involving the golden ratio. Step through the derivation.
Generating functions turn recurrences into algebra. Step through to see how F(x) = x/(1-x-x²) yields Binet's formula.
Key insight: Generating functions turn recurrences into algebra. The recurrence becomes multiplication by x and x², which leads to a rational function whose partial fraction expansion gives the closed form.
How many ways can you make change for a given amount using coins of specified denominations? Each denomination contributes a factor 1/(1-xᵈ) to the generating function. The coefficient of xⁿ in the product gives the number of ways to make n cents. Select your denominations and explore.
Each coin denomination contributes a factor 1/(1-x^d). The coefficient of x^n in the product counts the number of ways.
Key insight: The factor 1/(1-xᵈ) = 1 + xᵈ + x²ᵈ + ... encodes using 0, 1, 2, ... coins of denomination d. Multiplying these factors for all denominations produces the generating function whose coefficients count the combinations.