Finite J-fraction coefficients enumerate bounded weighted Motzkin step paths
ProvedAnalyticCombinatorics.Ch5.ContinuedFractions.coeff_JFraction_eq_stepPathSumanalytic-combinatoricscontinued-fractionslean4
Let be a commutative ring, let , and let be arbitrary weight families. For a family , put . Define formal series by
The reciprocals are formal inverses of series with constant coefficient . Let consist of all length- lists of up, down and level steps that start at height , finish at height , and stay at heights . Give an up step from to weight , a down step from to weight , and a level step at weight . Let be the product of its step weights, with empty product . Then
The height ceiling is finite and fixed in this identity; and are included. No positivity or analytic convergence assumption is required.
Preamble
import Definitions.Def_AnalyticCombinatorics_Ch5_ContinuedFractions_FlajoletStepPath
import Mathlib
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
/-!
# Ch5 §V — Flajolet's theorem on genuine step-list lattice paths (the bijection)
This completes the faithfulness upgrade begun in `FlajoletPathBijection.lean`: it proves the
weight-preserving bijection between the first-return-coded `MotzkinPath` type and genuine
lattice paths (`List Step` with the `Walk`/`ClosedMotzkin` validity), and assembles the capstone.
* `Walk_split` — drop a valid prefix (converse of `Walk_append`).
* `toSteps_surjective` — every closed lattice path is `toSteps` of some first-return code
(the parse, via `first_passage` — the cycle lemma).
* `balanced_split_eq` — first-return uniqueness (two balanced prefixes + `down` agree).
* `toSteps_injective` — distinct codes give distinct step lists.
* `coeff_JFraction_eq_stepPathSum` — **Flajolet's theorem on real lattice paths**: the `z^n`
coefficient of the bounded J-fraction is the weighted sum over all height-`≤h`, length-`n`
closed Motzkin step paths, with the first-return decomposition now a *theorem*, not a definition.
-/
open scoped BigOperators PowerSeries
open AnalyticCombinatorics AnalyticCombinatorics.Ch5 AnalyticCombinatorics.Ch5.ContinuedFractions
set_option maxHeartbeats 800000
variable {R : Type*} [CommRing R]
Formal statement
theorem AnalyticCombinatorics.Ch5.ContinuedFractions.coeff_JFraction_eq_stepPathSum (h n : ℕ) (a b c : ℕ → R) :
PowerSeries.coeff (R := R) n (JFraction h a b c)
= ∑ p ∈ closedMotzkinFinset h n, stepWeight a b c 0 p := by sorrySource
Human review
Confirmed by the mission captain (proposal self-audit).