TheoremStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck 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.

$(2 n + 1) C_{n} = (\binom{2 n + 1}{n})$ , a second derivation of the Catalan count

Statement

For every $n \in N$ , in $N$ ,

$(2 n + 1) C_{n} = (\binom{2 n + 1}{n}),$

where $C_{n}$ is the Catalan number (The Catalan number $C_{n} : = ∣ D_{n} ∣$ ).

This is a second derivation of the Catalan count, by a group action rather than by a reflection: the route runs through the cycle lemma (The cycle lemma (Dvoretzky–Motzkin): if every $a_{i} \leq 1$ and $∥ a ∥ = k \geq 1$ , then exactly $k$ of the $m$ cyclic shifts of $a$ have all partial sums positive) and the orbits of the cyclic shift, and it uses no reflection and no difference of binomial coefficients. The identity is consistent with $(n + 1) C_{n} = (\binom{2 n}{n})$ ( $(n + 1) C_{n} = (\binom{2 n}{n})$ ), and the consistency is the separate identity $(n + 1) (\binom{2 n + 1}{n}) = (2 n + 1) (\binom{2 n}{n})$ proved below.

Facts & Assumptions

Given: a natural number $n$ ; the set $W$ of words of length $2 n + 1$ over ${1, - 1}$ having exactly $n$ entries $- 1$ ; and the set $G$ of those $a \in W$ all of whose partial sums $\sum_{i < r} a_{i}$ , $1 \leq r \leq 2 n + 1$ , are positive.

[F1]

$C_{n} = ∣ D_{n} ∣$ (The Catalan number $C_{n} : = ∣ D_{n} ∣$ ).

[F2]

$D_{n}$ corresponds bijectively, through step words, to the set of ballot words of length $2 n$ , that is the words over a two-letter alphabet in which the two letters occur equally often and every prefix has at least as many of the first letter as of the second (Dyck paths of semilength $n$ ).

[F3]

$∥ a ∥ = \sum_{i < m} a_{i}$ , $(σ^{j} a)_{i} = a_{(i + j) m o d m}$ , and the finite sum satisfies $\sum_{i < 0} c_{i} = 0$ and $\sum_{i < r + 1} c_{i} = \sum_{i < r} c_{i} + c_{r}$ (Cyclic shifts of an integer word and its periodic partial-sum function).

[L1]

If $p, n^{'}, μ \in N$ and a word of length $p + n^{'} \geq 1$ has $p$ positions carrying $1$ and $n^{'}$ positions carrying $- μ$ , then its weight is $p - μ n^{'}$ ; and if $a$ has every letter at most $1$ and $∥ a ∥ = k \geq 1$ then exactly $k$ of the $m$ indices $j$ with $0 \leq j < m$ are such that $σ^{j} a$ has all its partial sums positive (The cycle lemma (Dvoretzky–Motzkin): if every $a_{i} \leq 1$ and $∥ a ∥ = k \geq 1$ , then exactly $k$ of the $m$ cyclic shifts of $a$ have all partial sums positive, clauses 2 and 1).

[L2]

If $\gcd (∥ a ∥, m) = 1$ then the stabiliser of $a$ under the shift action of $Z / m$ is ${[0]_{m}}$ and the orbit of $a$ has exactly $m$ elements (If $\gcd (∥ a ∥, m) = 1$ then the shift stabiliser of $a$ is trivial, so its orbit has exactly $m$ elements).

[L3]

For every letter $x$ the number of positions of $σ^{j} a$ carrying $x$ equals the number of positions of $a$ carrying $x$ , and $[j]_{m} \cdot a : = σ^{j} a$ is a left action of $Z / m$ on the words of length $m$ (Cyclic shifting is an action of $Z / m$ on the words of length $m$ over a set, clauses 2 and 3).

[L4]

For a left action of $G$ on $X$ the relation $x \sim y$ given by $y = g \cdot x$ for some $g \in G$ is an equivalence relation, its class at $x$ is the orbit of $x$ , and the distinct orbits partition $X$ (The orbits of a group action are the equivalence classes of $x \sim y$ iff $y = g \cdot x$ for some $g$ , and hence partition the acted-on set).

[L5]

For a finite set $A$ and $k \in N$ , $[A]^{k}$ is the set of $k$ -element subsets of $A$ , and $∣ [A]^{k} ∣ = (\binom{∣ A ∣}{k})$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

[L6]

If $I$ is finite and $(A_{i})_{i \in I}$ are pairwise disjoint finite sets, then $⋃_{i \in I} A_{i}$ is finite with $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ (The sum rule: a finite disjoint union is finite with $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ and $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ , and a sum over a finite index set splits along a partition, clause 2).

[L7]

For a constant natural number $c$ and a finite index set $S$ , $\sum_{i \in S} c = ∣ S ∣ \cdot c$ (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form, clause (c)).

[L8]

A subset of a finite set is finite (A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ , clause 1).

[L9]

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

[L10]

For $f : A \to B$ : $f$ is a bijection if and only if there is a function $g : B \to A$ with $g \circ f = Δ_{A}$ and $f \circ g = Δ_{B}$ ( $f : A \to B$ is a bijection if and only if there is a function $g : B \to A$ with $g \circ f = Δ_{A}$ and $f \circ g = Δ_{B}$ ; such a $g$ is unique, equals the inverse relation $f^{- 1}$ , and is itself a bijection).

[L11]

For $M, k \in N$ with $k \leq M$ : $(\binom{M}{k}) \cdot k! \cdot (M - k)! = M!$ ( $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ ).

[L12]

$M! \neq 0$ for every $M \in N$ , and $σ (M)! = M! \cdot σ (M)$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ ).

[L13]

For all $x, y, c \in N$ with $c \neq 0$ : if $x \cdot c = y \cdot c$ then $x = y$ (Cancellation for multiplication by a nonzero factor).

[L14]

$(n + 1) C_{n} = (\binom{2 n}{n})$ in $N$ ( $(n + 1) C_{n} = (\binom{2 n}{n})$ ).

[L15]

Integers $x$ and $y$ are coprime when $\gcd (x, y) = 1$ ; $x$ and $1$ are coprime for every integer $x$ , since $\gcd (x, 1) = 1$ , and the relation is symmetric (Coprime integers: $\gcd (a, b) = 1$ ).

Proof

technique · direct

1.1

The map sending $a \in W$ to ${j : 0 \leq j < 2 n + 1, a_{j} = - 1}$ is a bijection from $W$ onto the $n$ -element subsets of the $(2 n + 1)$ -element set ${0, \dots, 2 n}$ , its inverse sending a subset $T$ to the word with entry $- 1$ at the positions of $T$ and $1$ elsewhere; so $W$ is finite with $∣ W ∣ = (\binom{2 n + 1}{n})$ .

L5L9L10

1.2

Every $a \in W$ has $n$ positions carrying $- 1$ and the remaining $n + 1$ positions carrying $1$ , so its weight is $(n + 1) - n = 1$ by the box-and-circle clause of [L1] with $p = n + 1$ , $n^{'} = n$ and $μ = 1$ ; and every letter of $a$ is at most $1$ .

F3L1

1.3

The set $G$ is in bijection with $D_{n}$ , so $∣ G ∣ = C_{n}$ . A word $a \in G$ has first partial sum $a_{0} > 0$ , hence $a_{0} = 1$ ; deleting it leaves the word $w = a_{1} \dots a_{2 n}$ of length $2 n$ over ${1, - 1}$ , whose partial sums are $\sum_{i < r} w_{i} = (\sum_{i < r + 1} a_{i}) - 1 \geq 0$ and whose total is $∥ a ∥ - 1 = 0$ , so $w$ has $n$ entries of each sign and every prefix at least as many entries $1$ as $- 1$ : a ballot word of length $2 n$ under the relabelling of $1$ and $- 1$ as the two letters. Prepending $1$ inverts the deletion and carries a ballot word back into $G$ , since the partial sums then become $1$ plus a nonnegative number and the total becomes $1$ . With [F1], [F2], [L9] and [L10] this gives $∣ G ∣ = ∣ D_{n} ∣ = C_{n}$ .

F1F2F3L9L10

2.1

The shift action of $Z / (2 n + 1)$ restricts to $W$ , because shifting preserves the number of positions carrying each letter by [L3]. Since $\gcd (1, 2 n + 1) = 1$ , step 1.2 and [L2] make every stabiliser in $W$ trivial, so every orbit has exactly $2 n + 1$ elements and the $2 n + 1$ words $σ^{j} a$ with $0 \leq j < 2 n + 1$ are pairwise distinct.

L2L3L15step 1.2

3.1

Each orbit meets $G$ in exactly one word: by [L1] with $k = 1$ there is exactly one index $j$ in ${0, \dots, 2 n}$ with $σ^{j} a \in G$ , and by step 2.1 distinct indices give distinct words, so exactly one member of the orbit lies in $G$ . Hence $g \mapsto$ (orbit of $g$ ) is a bijection from $G$ onto the set of orbits, whose members partition $W$ by [L4]; $G$ is finite by [L8] and step 1.1, and [L6] with index set $G$ together with [L7] gives $∣ W ∣ = \sum_{g \in G} (2 n + 1) = ∣ G ∣ \cdot (2 n + 1)$ .

L1L4L6L7L8L9step 1.1step 2.1

4.1

Combining steps 1.1, 1.3 and 3.1 gives $(2 n + 1) C_{n} = ∣ W ∣ = (\binom{2 n + 1}{n})$ . For the consistency with [L14]: $n \leq 2 n + 1$ and $(2 n + 1) - n = n + 1$ , so [L11] gives $(\binom{2 n + 1}{n}) n! (n + 1)! = (2 n + 1)!$ , which with $(n + 1)! = (n + 1) n!$ from [L12] reads $(n + 1) (\binom{2 n + 1}{n}) \cdot n! n! = (2 n + 1)!$ ; and [L11] applied to $(\binom{2 n}{n})$ gives $(\binom{2 n}{n}) n! n! = (2 n)!$ , so $(2 n + 1) (\binom{2 n}{n}) \cdot n! n! = (2 n + 1) (2 n)! = (2 n + 1)!$ by [L12]. Cancelling the nonzero factor $n! n!$ by [L12] and [L13] gives $(n + 1) (\binom{2 n + 1}{n}) = (2 n + 1) (\binom{2 n}{n})$ , so multiplying the identity of this theorem by $n + 1$ and the identity of [L14] by $2 n + 1$ produces the same equation and the two closed forms agree. At $n = 0$ the theorem reads $C_{0} = (\binom{1}{0}) = 1$ .

L5L11L12L13L14step 1.1step 1.3step 3.1∎

Remarks

This is a different route, not a rearrangement. The reflection derivation matches paths that touch a level with paths from a reflected starting point; this one lets a cyclic group act on words and counts orbits. The two share only the definition of $C_{n}$ as a count of Dyck paths, and each yields a closed form the other does not produce directly: $(2 n + 1) C_{n} = (\binom{2 n + 1}{n})$ here and $(n + 1) C_{n} = (\binom{2 n}{n})$ there.
Where the coprimality is spent. Every word in $W$ has weight $1$ , and $1$ is coprime to every modulus, so no orbit is short and no word is counted twice. Without that the orbit count would not be $∣ W ∣$ divided by the length, and the argument would give an inequality rather than an identity.

Depends on

Used by

Dependency tree · two levels

87 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

N. Dershowitz and S. Zaks, "The Cycle Lemma and Some Applications", Europ. J. Combinatorics 11 (1990) 35–40, §2 (standard reference, not scraped)
A. Postnikov (notes by A. Lin), MIT 18.212 Algebraic Combinatorics, Spring 2019 (standard reference, not scraped)

(2n+1) Cn=(2n+1n)(2n+1)Cn​=(n2n+1​), a second derivation of the Catalan count