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.

$M_{n} = \sum_{k \in N, 2 k \leq n} (\binom{n}{2 k}) C_{k}$

Statement

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

$M_{n} = \sum_{k \in N, 2 k \leq n} (\binom{n}{2 k}) C_{k},$

the sum being over the finite index set ${k \in N : 2 k \leq n}$ (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form), with $M_{n}$ the Motzkin 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]

${M o t}_{n}$ is the set of lattice paths of length $n$ with steps in ${U, D, L}$ from $(0, 0)$ to $(n, 0)$ with $h (i) \geq 0$ at every index, and $M_{n} = ∣ {M o t}_{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$ ; in particular $\hat{h} (r) + r$ is even (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).

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

Proof

technique · direct

1.1

Let $v \in {M o t}_{n}$ have step word $w$ , put $A : = {j \in N : j < n, w_{j} \neq L}$ and let $\hat{w}$ be the word over ${U, D}$ obtained by reading the letters of $w$ at the positions of $A$ in increasing order. A level step leaves the height unchanged, so for every $i \leq n$ the height $h (i)$ of $v$ equals the height $\hat{h} (r)$ of the diagonal path traced by $\hat{w}$ at $r = ∣ A \cap i ∣$ , the number of non-level positions before $i$ ; and every $r$ with $0 \leq r \leq ∣ A ∣$ arises as such a count, taking $i$ to be $n$ or the position immediately after the $r$ -th member of $A$ . Hence $h (i) \geq 0$ for all $i$ if and only if $\hat{h} (r) \geq 0$ for all $r$ , and $h (n) = 0$ if and only if $\hat{h} (∣ A ∣) = 0$ .

F1F3

1.2

Consequently $∣ A ∣$ is even, say $∣ A ∣ = 2 k$ with $2 k \leq n$ , since $\hat{h} (∣ A ∣) = 0$ and $\hat{h} (r) + r$ is even by [F3]; and $\hat{w}$ is then a ballot word of length $2 k$ , so by [F2] it is the step word of a unique Dyck path of semilength $k$ .

F2F3

2.1

Let $P_{\hat{w}} \in D_{k}$ be the unique Dyck path whose step word is $\hat{w}$ , supplied by [F2]. The map $v \mapsto (k, A, P_{\hat{w}})$ is a bijection from ${M o t}_{n}$ onto the disjoint union over $k$ with $2 k \leq n$ of ${k} \times [n]^{2 k} \times D_{k}$ . Its inverse takes $(k, A, P)$ to the path of length $n$ whose step word carries the letters of the step word of $P$ at the positions of $A$ in increasing order and the letter $L$ elsewhere: by steps 1.1 and 1.2 that path lies in ${M o t}_{n}$ , and the two constructions undo one another, so [L1] and [L2] apply.

F2L1L2step 1.1step 1.2

3.1

The index set ${k : 2 k \leq n}$ is a subset of the finite set ${0, \dots, n}$ , hence finite by [L8], and for each of its members $[n]^{2 k}$ is finite with $(\binom{n}{2 k})$ elements by [L3] while $D_{k}$ is finite with $C_{k}$ elements by [F2]. So [L5] gives $∣ {k} \times [n]^{2 k} \times D_{k} ∣ = (\binom{n}{2 k}) C_{k}$ and [L4] with [L6] adds these over the index set; transporting along the bijection of step 2.1 by [L7] gives the stated identity. At $n = 0$ the index set is ${0}$ and the single term is $(\binom{0}{0}) C_{0} = 1$ ; at $n = 1$ it is ${0}$ again, giving $1$ ; at $n = 2$ the terms are $1$ and $(\binom{2}{2}) C_{1} = 1$ , giving $2$ ; at $n = 3$ they are $1$ and $(\binom{3}{2}) C_{1} = 3$ , giving $4$ ; and at $n = 4$ they are $1$ , $(\binom{4}{2}) C_{1} = 6$ and $(\binom{4}{4}) C_{2} = 2$ , giving $9$ .

F2L3L4L5L6L7L8step 2.1∎

Remarks

A bijective proof, and therefore a second route. The functional equation of $M (x) = 1 + x M (x) + x^{2} M (x)^{2}$ , and $2 x^{2} M (x) = 1 - x - (1 - 2 x - 3 x^{2})^{1 / 2}$ determines the same numbers, but nothing of it is used here: this argument deletes the level steps and reads what is left. It is also the identity that makes the Catalan numbers of this page count something other than Dyck paths.
Why the parity of $∣ A ∣$ is proved and not assumed. The subword at the non-level positions must return to height $0$ , and a diagonal path returns to its starting height only after an even number of steps. Assuming evenness would hide exactly the step that forces the summation index to be $2 k$ rather than $k$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

53 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.45) (standard reference, not scraped)

Mn=∑k∈N, 2k≤n(n2k)CkMn​=∑k∈N,2k≤n​(2kn​)Ck​