Polynomial multiplication, Fibonacci, and coin counting
Write a sequence as the coefficients of a power series and counting problems turn into algebra.
Click a result coefficient to see which pairs of input coefficients multiply and add to make it.
Polynomial multiplication is convolution: c_k = Σ a_i · b_(k-i). Click an index to see contributing pairs.
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.
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.
Key insight: Convolution is the algebraic engine behind generating functions. Many counting problems reduce to multiplying generating functions and reading off coefficients.
Step through the derivation, from the Fibonacci recurrence to an exact formula with the golden ratio.
Generating functions turn recurrences into algebra. Step through to see how F(x) = x/(1-x-x²) yields Binet's formula.
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.
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.
Select your coin denominations and a target amount, and read off how many ways there are to make change.
Each coin denomination contributes a factor 1/(1-x^d). The coefficient of x^n in the product counts the number of ways.
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.
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.
Spot a mistake or have an idea?