Catalan numbers

Mathematical statement

C_(n+1)=sum over i=0..n of C_i*C_(n−i), and C_n=binomial(2n,n)/(n+1)=binomial(2n,n)−binomial(2n,n+1). Before division, certify that n+1 divides the central binomial coefficient; integer truncation is not a substitute. The domain is n≥0 and the C_0/C_1 indexing conventions must not be mixed.

Representative formula (exact TeX)

C_n

Assumptions

• n is a bounded nonnegative safe integer.
• Closed forms use exact BigInt arithmetic with a remainder-zero certificate.

Symbol scope

• C_n — zero-based Catalan number

Intuition, definition, and misconceptions

The base value is C_0=1.

The recurrence sums every split.

Closed forms need exact divisibility and cross-checks.

Do not begin at C_1 while using a C_0 formula, or silently truncate the quotient.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Recurrence relation — Use the Catalan convolution.
• Binomial theorem — The closed forms use binomial coefficients.
• Basic counting principles — Finite combinatorial enumeration supports the sequence.
• Natural-number divisibility — The closed-form quotient is integral.

Verification boundary

Negative indices are outside the domain; this slice does not automatically prove every Catalan combinatorial bijection.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add analytic generating functions.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.