Small Group Tutorials

Here to help students catch up, keep up, and move ahead. Book a consultation here.

How to Learn Bostan–Mori: Generating Functions, Even–Odd Coefficients, N-th Terms and Fast Linear Recurrences

Wait, what? A recurrence can describe a sequence forever, yet you may want only one term so far away that stepping through every earlier term is absurd. Bostan–Mori is one of the cleanest examples of how advanced algorithms change the question instead of merely speeding up the obvious procedure.

Quick Read

A linear recurrence can be encoded as a rational generating function P(x)/Q(x).
Bostan–Mori repeatedly halves the target index by separating even and odd coefficients.
With fast polynomial multiplication, the n-th term can be computed in O(M(d) log n) arithmetic operations for recurrence order d.
The professional skill is not memorising formulas. It is learning how representation changes turn an apparently sequential problem into logarithmic-depth algebra.

One-sentence answer: learn Bostan–Mori by first mastering linear recurrences and generating functions, then tracing how parity filtering reduces the requested coefficient index by half at each round, and finally connecting that invariant to polynomial multiplication, modular arithmetic and production implementation.

1. The Beginner Problem: Why Not Just Generate the Sequence?

Suppose a sequence satisfies a recurrence such as a(n)=a(n−1)+a(n−2). If you need a(100), ordinary dynamic programming is perfectly sensible. If you need a(10^18), it is not. The first professional habit is therefore to ask what the input scale does to the obvious method.

Linear recurrences have structure. The next value is not arbitrary; it is a fixed linear combination of a bounded number of previous values. That means the whole infinite sequence can be represented compactly. Bostan–Mori exploits that compact representation.

2. The Representation Shift: From Sequence to Generating Function

Write the sequence as a formal power series A(x)=a0+a1x+a2x²+… . A linear recurrence of fixed order implies that A(x) can be expressed as a rational function P(x)/Q(x), where Q records the recurrence coefficients and P adjusts for the initial terms.

This is the first major conceptual threshold. A generating function is not merely a clever notation. It turns recurrence constraints into algebraic constraints. Instead of asking, “How do I walk forward through the sequence?”, we can ask, “What is the coefficient of x^n in P(x)/Q(x)?”

3. The Core Trick: Multiply by Q(−x)

The method forms Q(−x), multiplies numerator and denominator by it, and uses the fact that Q(x)Q(−x) contains only even powers of x. Why? Terms of odd degree cancel. That makes the denominator effectively a polynomial in x².

The numerator P(x)Q(−x) contains both even and odd coefficients. If the target index n is even, only the even-indexed coefficients matter. If n is odd, only the odd-indexed coefficients matter. We keep the relevant parity class, replace x² by x, and reduce n to floor(n/2).

That is the beating heart of Bostan–Mori: one algebraic round halves the coefficient index.

4. Trace a Tiny Example Before Writing Code

For the Fibonacci recurrence F(n)=F(n−1)+F(n−2), the denominator is Q(x)=1−x−x². The generating function for the standard initial values is x/(1−x−x²). To find a distant coefficient, construct Q(−x)=1+x−x², multiply P and Q by that transformed denominator, then select either the even or odd coefficients of the new numerator according to the parity of n. The denominator becomes parity-clean and the target index shrinks.

Do this by hand for a small n such as 11. Write every polynomial coefficient. Mark the parity you retain. If you cannot explain why the requested coefficient is preserved after the transformation, you are not yet ready to optimize the code.

5. The Invariant You Must Be Able to Say Out Loud

At every iteration, the current rational function P(x)/Q(x) represents a power series whose coefficient at the current target index is exactly the original answer we want. The parity transformation replaces that coefficient problem with an equivalent coefficient problem at half the index.

This invariant is more important than the loop syntax. Professional algorithm work depends on invariants because optimizations often rearrange data aggressively. The invariant is what lets you decide whether a faster implementation is still the same algorithm.

6. Complexity: Where the Speed Actually Comes From

If the recurrence order is d, the relevant polynomials stay degree O(d). Each round needs polynomial products and parity extraction, while the target index is divided by two. Therefore there are O(log n) rounds. If polynomial multiplication costs M(d), the arithmetic complexity is O(M(d) log n).

With schoolbook multiplication, M(d)=O(d²). With FFT- or NTT-based multiplication in suitable settings, M(d) can be much closer to quasi-linear. This is why Bostan–Mori belongs naturally in a larger learning path that includes convolution, modular arithmetic and fast polynomial operations.

7. Implementation Ladder: Beginner to Professional

Stage 1 — recurrence literacy: generate terms with a direct loop and verify initial conditions.
Stage 2 — generating functions: derive P and Q for several recurrences by hand.
Stage 3 — parity mechanics: implement multiplication and even/odd coefficient extraction with plain arrays.
Stage 4 — modular version: compute over a prime field and test against dynamic programming for small n.
Stage 5 — fast multiplication: replace quadratic convolution with NTT/FFT only after the simple version is trusted.
Stage 6 — reusable recurrence engine: separate recurrence construction, polynomial arithmetic, coefficient query and test infrastructure.

8. Common Failure Modes

Incorrectly constructing P from the recurrence and initial terms.
Reversing sign conventions in Q(x).
Choosing the wrong parity slice after multiplying P(x)Q(−x).
Forgetting coefficient normalization in modular arithmetic.
Assuming FFT rounding is harmless for exact integer problems.
Optimizing multiplication before validating the algebraic invariant.

9. How to Debug Bostan–Mori Systematically

Use differential testing. Generate random low-order recurrences over a small prime modulus. Compute the first few hundred terms with direct dynamic programming. Then compare Bostan–Mori answers for many random indices in that range. When a mismatch appears, print the current P, Q, n and parity at every iteration.

This is a better learning strategy than staring at the final wrong number. Debugging research in programming education repeatedly shows the importance of explicit fault-location strategies and robust mental models; advanced algorithms reward the same discipline.

10. A Professional Mental Model

Do not remember Bostan–Mori as “that recurrence trick with Q(−x).” Remember it as a representation pipeline:

recurrence → rational generating function;
coefficient query → parity-filtered coefficient query;
large index → half-sized index;
repeated halving → logarithmic number of rounds;
polynomial arithmetic → the real implementation cost.

That mental model transfers. Many advanced algorithms become understandable when you ask which representation makes the expensive dimension shrink.

11. Practice Sequence

Derive P/Q for Fibonacci and a third-order recurrence.
Hand-trace one complete Bostan–Mori query for a two-digit n.
Implement the quadratic-polynomial version.
Prove to yourself why Q(x)Q(−x) has only even powers.
Write randomized differential tests.
Add modular arithmetic.
Only then integrate an NTT or other fast convolution routine.
Benchmark by recurrence order d and index size n separately.

12. Teaching Note

For learners seeing this algorithm for the first time, begin with a worked example and ask them to predict which coefficients survive before running any code. Then let them modify one part at a time: recurrence coefficients, target parity, polynomial degree. This predict–run–investigate–modify progression is well aligned with evidence from programming education on worked examples, self-explanation and scaffold fading.