CorollaryStatement: Literature-sourcedProof: AI-generatedSession-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.

$R_{n} = \sum_{k = 0}^{n} (\binom{n + k}{2 k}) C_{k}$

Statement

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

$R_{n} = \sum_{k = 0}^{n} (\binom{n + k}{2 k}) C_{k},$

the sum being over the finite index set ${0, 1, \dots, n}$ (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form), with $R_{n}$ the large Schröder numbers (Motzkin paths, Schröder paths, the Motzkin numbers $M_{n}$ , the large Schröder numbers $R_{n}$ , and their generating functions) and $C_{k}$ the Catalan numbers (The Catalan number $C_{n} : = ∣ D_{n} ∣$ ).

Facts & Assumptions

Given: a natural number $n$ .

[F1]

${S c h}_{n}$ is the set of lattice paths with steps in ${U, D, L_{2}}$ from $(0, 0)$ to $(2 n, 0)$ with $h (i) \geq 0$ at every index; such a path with $k$ up steps has $k$ down steps, $n - k$ level steps and $n + k$ steps in all, with $0 \leq k \leq n$ ; and $R_{n} = ∣ {S c h}_{n} ∣$ is finite (Motzkin paths, Schröder paths, the Motzkin numbers $M_{n}$ , the large Schröder numbers $R_{n}$ , and their generating functions).

[F2]

$D_{k}$ corresponds bijectively, through step words, to the ballot words of length $2 k$ , that is the words over ${U, D}$ with equally many letters of each kind in which every prefix has at least as many $U$ as $D$ ; and $C_{k} = ∣ D_{k} ∣$ (Dyck paths of semilength $n$ , The Catalan number $C_{n} : = ∣ D_{n} ∣$ ).

[F3]

For a diagonal path of length $ℓ$ from $(0, 0)$ with step word $\hat{w}$ and $μ (r)$ the number of up steps among the first $r$ , the height is $\hat{h} (r) = 2 μ (r) - r$ (Diagonal lattice paths with steps $U = (1, 1)$ and $D = (1, - 1)$ , and the height function).

[L1]

For a step set $S$ , a point $P$ and $ℓ \in N$ , the map sending a lattice path to its step word is a bijection $L_{S} (P; ℓ) \to S^{ℓ}$ (For each start point the step word is a bijection onto $S^{n}$ ).

[L2]

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).

[L3]

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

[L4]

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).

[L5]

If $A$ and $B$ are finite then $A \times B$ is finite and $∣ A \times B ∣ = ∣ A ∣ \cdot ∣ B ∣$ (The product rule: $∣ A \times B ∣ = ∣ A ∣ ∣ B ∣$ , and $∣ \prod_{i < m} A_{i} ∣ = \prod_{i < m} ∣ A_{i} ∣$ , clause 1).

[L6]

For a finite index set $S$ and $a : S \to N$ the sum $\sum_{i \in S} a_{i}$ is defined (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form).

[L7]

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).

Proof

technique · direct

1.1

Let $v \in {S c h}_{n}$ with $k$ up steps. By [F1] it has exactly $n + k$ steps, of which $2 k$ are not level, so the number of positions available to the non-level steps is $n + k$ and depends on $k$ ; that dependence is the whole difference from the Motzkin case, where the number of positions is $n$ for every $k$ . Let $A$ be the set of non-level positions, a $2 k$ -element subset of ${0, \dots, n + k - 1}$ , and let $\hat{w}$ be the word over ${U, D}$ read off the letters of the step word of $v$ at the positions of $A$ in increasing order. A level step leaves the height unchanged, so the height of $v$ at any index equals the height of the diagonal path traced by $\hat{w}$ after the corresponding number of non-level steps, and every such number arises; hence the height condition on $v$ says exactly that $\hat{h} \geq 0$ throughout and $\hat{h} (2 k) = 0$ , so $\hat{w}$ is a ballot word of length $2 k$ and by [F2] the step word of a unique Dyck path of semilength $k$ .

F1F2F3

2.1

For each $k$ with $0 \leq k \leq n$ the map just described is a bijection from the set of $v \in {S c h}_{n}$ having exactly $k$ up steps onto $[n + k]^{2 k} \times D_{k}$ , where $[n + k]^{2 k}$ is the set of $2 k$ -element subsets of ${0, \dots, n + k - 1}$ . Its inverse takes $(A, P)$ to the path whose step word has length $n + k$ , carries the letters of the step word of $P$ at the positions of $A$ in increasing order and the letter $L_{2}$ elsewhere: that word has $k$ up steps, $k$ down steps and $n - k$ level steps, hence horizontal extent $2 k + 2 (n - k) = 2 n$ , and by step 1.1 its heights are nonnegative and it ends at height $0$ , so it lies in ${S c h}_{n}$ and has exactly $k$ up steps. The two constructions undo one another, so [L1] and [L2] apply.

F1F2L1L2step 1.1

3.1

The sets of $v \in {S c h}_{n}$ with exactly $k$ up steps, for $0 \leq k \leq n$ , are pairwise disjoint with union ${S c h}_{n}$ by [F1]. Each is finite with $(\binom{n + k}{2 k}) C_{k}$ elements, by step 2.1 with [L3], [L5] and [L7], and adding them over the finite index set ${0, \dots, n}$ with [L4] and [L6] gives the stated identity. At $n = 0$ the single term is $(\binom{0}{0}) C_{0} = 1$ ; at $n = 1$ the terms are $(\binom{1}{0}) C_{0} = 1$ and $(\binom{2}{2}) C_{1} = 1$ , giving $2$ ; at $n = 2$ they are $1$ , $(\binom{3}{2}) C_{1} = 3$ and $(\binom{4}{4}) C_{2} = 2$ , giving $6$ ; and at $n = 3$ they are $1$ , $(\binom{4}{2}) C_{1} = 6$ , $(\binom{5}{4}) C_{2} = 10$ and $(\binom{6}{6}) C_{3} = 5$ , giving $22$ .

F1L3L4L5L6L7step 2.1∎

Remarks

The binomial coefficient is $(\binom{n + k}{2 k})$ and not $(\binom{n}{2 k})$ . A Schröder path of half-length $n$ with $k$ up steps has $n + k$ steps, because a level step covers two units of horizontal extent while an up or a down step covers one. So the positions the non-level steps may occupy are $n + k$ in number, and that number moves with $k$ . In the Motzkin case every step has width $1$ , the number of positions is $n$ for every $k$ , and the coefficient is $(\binom{n}{2 k})$ .
The same deletion, twice. The argument is the level-step deletion of $M_{n} = \sum_{k \in N, 2 k \leq n} (\binom{n}{2 k}) C_{k}$ ; only the count of available positions changes. Splitting by the number of up steps is what makes that count available, and it is why the sum here is indexed by $k$ from $0$ to $n$ rather than by the condition $2 k \leq n$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

51 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

C. Krattenthaler, "Lattice Path Enumeration", ch. 10 of the Handbook of Enumerative Combinatorics, §10.8, Corollary 10.8.2, equation (10.46) (standard reference, not scraped)

Rn=∑k=0n(n+k2k)CkRn​=∑k=0n​(2kn+k​)Ck​