AFTD Auto-Formalizing Theoretical Domains

motzkin_number

def

The n-th Motzkin number M_n is defined by M_0 = 1 and M_{n+1} = M_n + ∑_{i=0}^{n-1} M_i M_{n-1-i}.

Statement

def motzkin_number : ℕ → ℕ
Defined in
arXiv:2610.32824 Definition 1.2
Verified
26 Oct 2026
Axioms
none listed

Read back from the Lean

The function motzkin_number : ℕ → ℕ defined recursively by: - motzkin_number 0 = 1 - for all $n : ℕ$, motzkin_number (n + 1) = motzkin_number n + ∑ i : Fin n, motzkin_number i.val * motzkin_number (n - 1 - i.val) (i.e., motzkin_number n plus the sum of motzkin_number i * motzkin_number (n - 1 - i) for $i$ from $0$ to $n - 1$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The n-th Motzkin number defined recursively. -/
def motzkin_number : ℕ → ℕ
| 0 => 1
| n + 1 => motzkin_number n + ∑ i : Fin n, motzkin_number i.val * motzkin_number (n - 1 - i.val)
See it in the graphDiscuss this resultChallenge it