AFTD Auto-Formalizing Theoretical Domains

fibonacci_word

def

The sequence of binary Fibonacci words F_n over Bool, defined by F_0 = [false], F_1 = [false, true], and F_{n+2} = F_{n+1} ++ F_n.

Statement

def fibonacci_word : ℕ → List Bool
Defined in
Algebraic Combinatorics on Words, Chapter 2
Verified
29 Oct 2026
Axioms
none listed
Used by 4

Read back from the Lean

The definition of a function fibonacci_word : ℕ → List Bool defined recursively on natural numbers by: - fibonacci_word 0 = [false] - fibonacci_word 1 = [false, true] - fibonacci_word (n + 2) = fibonacci_word (n + 1) ++ fibonacci_word n for all $n \in \mathbb{N}$, where ++ is list concatenation.

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 finite Fibonacci word over {0, 1} (represented as false and true). -/
def fibonacci_word : ℕ → List Bool
| 0 => [false]
| 1 => [false, true]
| n + 2 => fibonacci_word (n + 1) ++ fibonacci_word n
See it in the graphDiscuss this resultChallenge it