LemmaStatement: AI-generatedProof: AI-generated

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.

Dyck words and elementary Catalan growth

Statement

A Dyck word of length $2 k$ , for integer $k \geq 1$ , is a sequence of $k$ symbols $+ 1$ and $k$ symbols $- 1$ whose every initial partial sum is nonnegative. Write $C_{k}$ for the number of these words. Then $C_{k} = (\binom{2 k}{k}) / (k + 1)$ and

$\frac{4^{k}}{(2 k + 1) (k + 1)} \leq C_{k} \leq 4^{k} .$

In the real-sequence sense of Sequences, convergence, Cauchyness, monotonicity, boundedness and closed intervals in an arbitrary ordered field, $C_{k}^{1 / (2 k)} \to 2$ . The integer $(\binom{m}{r}) = m! / (r! (m - r)!)$ counts the $r$ -element subsets of an $m$ -element set, where $m! = 1 \cdot 2 \dots m$ and $0! = 1$ .

Facts & Assumptions

[F1]

A real sequence converges to a real number when, for every positive tolerance, all sufficiently late terms lie within that tolerance (Sequences, convergence, Cauchyness, monotonicity, boundedness and closed intervals in an arbitrary ordered field).

[F2]

For $a > 0$ and integer $N \geq 1$ , $a^{1 / N}$ denotes the unique positive $N$ -th root of $a$ , as a rational power (Rational powers aʳ of a positive base).

[F3]

For positive real bases and rational exponents, rational powers are positive and obey product, inverse and composition laws (Laws of rational exponents); a positive rational power is increasing in its positive base (Monotonicity of r ↦ aʳ and of a ↦ aʳ).

[F4]

For real $x, y$ and integer $n \geq 0$ , $(x + y)^{n} = \sum_{j = 0}^{n} (\binom{n}{j}) x^{j} y^{n - j}$ (The binomial theorem in ℝ: (x+y)ⁿ = ∑_k<n+1 iotaC(n, k) xᵏ y^ n-k).

[F5]

The natural numbers are unbounded in the real numbers: for every real $B$ there is a natural number $K > B$ (The Dedekind reals are Archimedean).

[F6]

For natural numbers $m, r$ , $(\binom{m}{r})$ is the number of $r$ -element subsets of any $m$ -element set (The set [A]ᵏ of k-element subsets and the binomial coefficient C(n, k) := | [n]ᵏ|).

Proof

Given: The objects and hypotheses in the statement.

Goal: Establish every assertion in the statement.

1.1givenF6constructalgebra

By [F6], there are $(\binom{2 k}{k})$ balanced words: choose the positions of the $+ 1$ symbols. Reflect every symbol through the first time a balanced word has partial sum $- 1$ . This maps the words failing the nonnegative condition bijectively to words with total sum $2$ , having $k + 1$ positive symbols and $k - 1$ negative symbols. The inverse reflects through the first partial sum $1$ of such a word. Thus $C_{k} = (\binom{2 k}{k}) - (\binom{2 k}{k + 1}) = (\binom{2 k}{k}) / (k + 1)$ . The subset formula follows by counting ordered lists of distinct selected elements and dividing by their $r!$ orders.

1.2F4F5algebrachoose

Put $D_{k} = (2 k + 1) (k + 1)$ . For $k \geq 2$ , the formula $(\binom{2 k}{3}) = (2 k) (2 k - 1) (2 k - 2) / 6$ gives $(\binom{2 k}{3}) \geq k^{3} / 3$ , while $D_{k} \leq 6 k^{2}$ , so $(\binom{2 k}{3}) / D_{k} \geq k / 18$ . Fix $δ > 0$ . By [F5], choose a natural number $K > 1 + 18 δ^{- 3}$ . For every integer $k \geq K$ , one has $k \geq 2$ and $(k / 18) δ^{3} > 1$ . By [F4] and nonnegativity of all binomial terms, $(1 + δ)^{2 k} \geq (\binom{2 k}{3}) δ^{3} > D_{k}$ for all such $k$ .

2.1F4step 1.1algebra

By [F4] with $x = y = 1$ and $n = 2 k$ , the sum of all $2 k + 1$ binomial coefficients in row $2 k$ is $2^{2 k} = 4^{k}$ ; equivalently, count every subset according to its size. The central coefficient is maximal: consecutive coefficients have ratio $(2 k - r) / (r + 1)$ , at least one up to the center and at most one thereafter. Hence $4^{k} / (2 k + 1) \leq (\binom{2 k}{k}) \leq 4^{k}$ , giving the displayed inequalities.

3.1F1F2F3step 2.1step 1.2algebrachoose∎

Since $D_{k} > 0$ and $1 + δ > 0$ , [F2] and [F3] applied to step 1.2 give $D_{k}^{1 / (2 k)} \leq 1 + δ$ for all $k \geq K$ . The bounds of step 2.1 imply $C_{k} > 0$ ; by the positive-root order, product, inverse and composition laws in [F2] and [F3], $2 / (1 + δ) \leq 2 / D_{k}^{1 / (2 k)} \leq C_{k}^{1 / (2 k)} \leq 2$ . Given any real tolerance $ε > 0$ , set $δ = ε / 4 > 0$ and choose $K$ as in step 1.2. For every $k \geq K$ , $∣ C_{k}^{1 / (2 k)} - 2 ∣ \leq 2 - 2 / (1 + δ) = 2 δ / (1 + δ) < ε$ . This is the limit assertion by [F1].

Depends on

Used by · 3

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.