Use formal power series to encode counting and recurrences.
Loading your saved responses…
Try
A sequence can be stored as coefficients: A(x)=a₀+a₁x+a₂x²+… . The variable x marks size; the coefficient records how many objects of that size exist. It is not the sequence index supplied as an ordinary numerical input.
Predict
Predict the coefficient rule for multiplying two series. To obtain degree n, pair degrees k and n−k and add their products. This finite sum is convolution. For formal power series, each coefficient depends on finitely many terms, so no numerical convergence assumption is needed.
Experiment
Multiply (1+x+x²) by (1+x+x²+x³) on paper. Interpret the coefficient of x³ as ways to split a total of three into a first contribution from 0 to 2 and a second from 0 to 3. List the three exponent pairs to check the algebra.
Understand
Worked counting sequence: compositions into parts 1 and 2 have a₀=1 (the empty composition), a₁=1, and aₙ=aₙ₋₁+aₙ₋₂. Separate a composition by its first part; the two branches are disjoint. Multiplying A(x) by 1−x−x² cancels every positive-degree coefficient, leaving 1. Thus A(x)=1/(1−x−x²) formally.
Likewise (1−x)(1+x+x²+…)=1 coefficient by coefficient. A series with nonzero constant term has a formal multiplicative inverse, determined recursively. If x is later assigned a number, convergence becomes a different question.
Invalid interpretation: A(5) is a₅. The coefficient a₅ must be extracted; evaluation, when meaningful, combines all coefficients with powers of 5.
Apply
State what a coefficient counts and explain how products correspond to combined objects. Check the constant term carefully: empty objects often supply the one needed to make recurrence identities correct.
Continue
Depth: ordinary generating functions suit many size-counted objects; exponential generating functions use aₙ/n! and are useful for labeled structures. Partial fractions, Catalan families and multivariate series belong to the later combinatorics course.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Find the coefficient of x³ in (1+x+x²)(1+x+x²+x³).
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
How many ordered compositions of 5 into parts 1 and 2 are there?
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
In an ordinary generating function A(x)=Σaₙxⁿ, aₙ is:
The coefficient of xⁿ in A(x)B(x) is:
Prove formally that (1−x)(1+x+x²+…)=1 and explain why numerical convergence is not needed for this coefficient identity.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For a₀=1,a₁=1,aₙ=aₙ₋₁+aₙ₋₂, derive A(x)=1/(1−x−x²) as a formal generating function.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
