ExampleConstruction: AI-generatedVerification: AI-adaptedprecheck passaudited 2026-08-26

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The first coefficients of the Catalan generating function

Example

Up to degree $5$ ,

$C (x) = 1 + x + 2 x^{2} + 5 x^{3} + 14 x^{4} + 42 x^{5} + O (x^{6}),$

$1 - 2 x C (x) = 1 - 2 x - 2 x^{2} - 4 x^{3} - 10 x^{4} - 28 x^{5} + O (x^{6}) .$

Facts & Assumptions

Given: the Catalan generating function $C (x)$ .

[L1]

$C (x) = 1 + x C (x)^{2}$ ( $C (x) = 1 + x C (x)^{2}$ ).

[L2]

$(1 - 2 x C (x))^{2} = 1 - 4 x$ ( $2 x C (x) = 1 - (1 - 4 x)^{1 / 2}$ , where $(1 - 4 x)^{1 / 2}$ is the unique square root with constant coefficient $1$ ).

[L3]

$(1 - 4 x)^{1 / 2} = 1 - 2 x - 2 x^{2} - 4 x^{3} - 10 x^{4} - 28 x^{5} + O (x^{6})$ ( $[x^{k}] (1 - 4 x)^{1 / 2} = - \frac{2}{k} (\binom{2 k - 2}{k - 1})$ for $k \geq 1$ , and $1$ for $k = 0$ ).

Verification

technique · direct

1.1L1

Using the coefficients $1, 1, 2, 5, 14, 42$ , the Cauchy product gives $C (x)^{2} = 1 + 2 x + 5 x^{2} + 14 x^{3} + 42 x^{4} + 132 x^{5} + O (x^{6})$ , so $1 + x C (x)^{2}$ agrees with $C (x)$ through degree $5$ , as [L1] says it should.

1.2L3

The displayed coefficients of $1 - 2 x C (x)$ are exactly those of [L3], so the closed form predicts $1 - 2 x C (x) = (1 - 4 x)^{1 / 2}$ modulo $x^{6}$ .

2.1L2step 1.2∎

Squaring $1 - 2 x - 2 x^{2} - 4 x^{3} - 10 x^{4} - 28 x^{5}$ gives $1 - 4 x$ modulo $x^{6}$ , which matches [L2].

Remarks

This is the finite coefficient check behind the formal closed form. The theorem on the A page proves the identity in all degrees; the example shows the first place where the numbers become recognisably Catalan.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

21 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

A. Postnikov (notes by A. Lin), MIT 18.212 Algebraic Combinatorics, Spring 2019 (standard reference, not scraped)