Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 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.

R(x)=1+x R(x)+x R(x)2, and 2x R(x)=1−x−(1−6x+x2)1/2

Statement

In Q⟦x⟧ the generating function of the large Schröder numbers (Motzkin paths, Schröder paths, the Motzkin numbers Mn, the large Schröder numbers Rn, and their generating functions) satisfies

R=1+x R+x R2,

and, with (1−6x+x2)1/2 the formal binomial power of Formal exponential, logarithm, and binomial powers over a commutative Q-algebra,

2x R=1−x−(1−6x+x2)1/2,

the series 1−x−2xR being the unique element of 1+xQ⟦x⟧ whose square is 1−6x+x2 (Every 1+u with u∈xR⟦x⟧ has a unique kth root with constant coefficient 1 in a commutative Q-algebra).

Facts & Assumptions

[F1]

Schm is the set of lattice paths with steps in {U,D,L2}, where U=(1,1), D=(1,−1) and L2=(2,0), from (0,0) to (2m,0) with h(i)≥0 at every index; such a path with k up steps has k down steps, m−k level steps and m+k steps in all, with 0≤k≤m; Rm=∣Schm∣ is finite; R0=1 and R1=2, the two paths of half-length 1 having step words L2 and UD; and R(x)=∑m≥0Rmxm (Motzkin paths, Schröder paths, the Motzkin numbers Mn, the large Schröder numbers Rn, and their generating functions).

[F2]

A natural number written where a rational is expected denotes its image under an injective embedding preserving addition, multiplication and finite sums, and Q⟦x⟧ is a commutative Q-algebra (The Catalan generating function C(x)=∑n≥0Cnxn in Q⟦x⟧).

[L1]

For a step set S, a point P and ℓ∈N, the map sending a lattice path to its step word is a bijection LS(P;ℓ)→Sℓ (For each start point the step word is a bijection onto Sn).

[L2]
[L3]

If A and B are finite and disjoint then ∣A∪B∣=∣A∣+∣B∣; and if I is finite and (Ai)i∈I are pairwise disjoint finite sets then ∣⋃i∈IAi∣=∑i∈I∣Ai∣ (The sum rule: a finite disjoint union is finite with ∣A∪B∣=∣A∣+∣B∣ and ∣⋃i∈IAi∣=∑i∈I∣Ai∣, and a sum over a finite index set splits along a partition, clauses 1 and 2).

[L4]

If A and B are finite then A×B is finite and ∣A×B∣=∣A∣⋅∣B∣ (The product rule: ∣A×B∣=∣A∣ ∣B∣, and ∣∏i<mAi∣=∏i<m∣Ai∣, clause 1).

[L5]

For a finite index set S and a:S→N the sum ∑i∈Sai is defined (The sum ∑i∈Sai over a finite index set, and its product form).

[L6]

[xm](f+g)=[xm]f+[xm]g; f=g if and only if [xm]f=[xm]g for every m; [xm](xkf)=[xm−k]f for k≤m and 0 for k>m; and [xm](fg)=∑i=0m[xi]f [xm−i]g (Coefficient extraction is R-linear, separates formal series, shifts under multiplication by xk, and converts products to finite convolution).

[L7]

For a commutative Q-algebra R′, u∈xR′⟦x⟧ and k≥1, there is a unique v∈1+xR′⟦x⟧ with vk=1+u, namely v=(1+u)1/k (Every 1+u with u∈xR⟦x⟧ has a unique kth root with constant coefficient 1 in a commutative Q-algebra).

[L8]

For u∈xR′⟦x⟧ and c∈R′ the formal binomial power is (1+u)c:=exp⁡(clog⁡(1+u)) (Formal exponential, logarithm, and binomial powers over a commutative Q-algebra).

[L9]

The coefficientwise sum and Cauchy product make Q⟦x⟧ a commutative ring (Cauchy multiplication makes R⟦x⟧ a commutative ring containing R[x] as the finitely supported subring).

[L10]

If A is finite and f:A→B is a bijection then B is finite and ∣B∣=∣A∣ (The cardinality ∣A∣ of a finite set).

[L11]

Every nonempty subset S⊆N has a least element (The well-ordering principle).

Proof

technique · direct
1.1F1L1L2L11

First-return decomposition. Let v∈Schn+1, of length ℓ, with step word w and heights h. Its first step is not D, so it is L2 or U. If it is L2 then translating the remaining path by (−2,0) gives a member of Schn, since its endpoints become (0,0) and (2n,0) and its heights are unchanged. If it is U then h(1)=1; the set of positive indices j≤ℓ with h(j)=0 contains ℓ, so by [L11] it has a least element τ≥2, and h(τ−1)≥1 by minimality while h(τ)=0, so the step at τ lowers the height and is therefore D, with h(τ−1)=1. Translating the portion of v from the index 1 to the index τ−1 by (−1,−1) gives a path from (0,0) whose heights are h(1+j)−1≥0 and which returns to height 0; its numbers of up and down steps are therefore equal, so its horizontal extent is even, say 2i, and it lies in Schi. Since the D step at τ has width 1, the first coordinate at τ is 2i+2, so translating the portion from τ to ℓ by (−2i−2,0) gives a member of Schn−i, and 0≤i≤n. Conversely, prepending L2 to a member of Schn, and sending (i,P,Q) to the path with step word U, that of P, D, that of Q, produce members of Schn+1 whose first-return data are the ones started from, because the heights strictly inside the first block are at least 1; the two constructions are two-sided inverses, so by [L1] and [L2] the set Schn+1 is in bijection with the disjoint union of Schn and the sets {i}×Schi×Schn−i for 0≤i≤n.

2.1F1L3L4L5L10step 1.1

The index range is where this differs from the Motzkin case. A U and its matching D have width 1 each, so together they consume two units of horizontal extent and therefore exactly one unit of half-length; the inner and outer blocks then carry half-lengths i and n−i with i+(n−i)=n, so the convolution index runs over all of {0,…,n} and not only over {0,…,n−1}. Counting the two sides of step 1.1 with [F1], [L3], [L4], [L5] and [L10] gives, in N, Rn+1=Rn+∑i=0nRiRn−i, the sum being over the finite index set {0,…,n}. At n=0 the sum has the single term R0R0=1, so R1=R0+1=2, matching the two paths with step words L2 and UD. At n=1 it gives R2=R1+R0R1+R1R0=6, at n=2 it gives R3=R2+R0R2+R1R1+R2R0=22, and at n=3 it gives R4=R3+R0R3+R1R2+R2R1+R3R0=90.

3.1F1F2L6L9step 2.1

Comparing coefficients gives the functional equation. At the index 0: [x0](1+xR+xR2)=1 by [L6], and [x0]R=R0=1. At an index n+1: [xn+1](xR)=[xn]R=Rn and [xn+1](xR2)=[xn](R2)=∑i=0nRiRn−i by the shift and Cauchy-product clauses of [L6], and the sum of the two is Rn+1 by step 2.1. Extensionality in [L6] gives R=1+xR+xR2.

4.1L6L7L8L9step 3.1∎

Rearranging step 3.1 in the commutative ring Q⟦x⟧ gives xR2+(x−1)R+1=0, and hence (1−x−2xR)2=(x−1)2+4x(xR2+(x−1)R)=(x−1)2−4x=1−6x+x2. The series 1−x−2xR has coefficient 1 at the index 0, so it lies in 1+xQ⟦x⟧, and 1−6x+x2=1+u with u=−6x+x2∈xQ⟦x⟧; by the uniqueness clause of [L7] with k=2 it is therefore (1−6x+x2)1/2 as defined in [L8], which gives 2xR=1−x−(1−6x+x2)1/2. No division by 2x occurs, and none is available.

Remarks

  • One index range, and it is the whole content. Everything else in this proof is the Motzkin argument with the level step widened. The Motzkin convolution stops at n−1 because a U with its D costs two units of the index, and the Schröder convolution runs to n because in half-length it costs one. A proof that copied the Motzkin range would give a false equation whose first wrong value is R1.

  • What the source proves and what is proved here. The statement is the source's, in the cleared form; its derivation there goes through a continued fraction, and the first-return argument above is written locally, exactly as in the Motzkin case.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

61 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