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
- fibonacci_singular_wordThe j-th singular word S_j, defined for j ≥ 0 by prefixing the last symbol of F_{j-1} (which is true if j is even and false if j is odd)…
- fibonacci_attractor_basis_seven_coverage_distinctThe cardinality of the image under word_occurrence_coverage (fibonacci_word 7) of fibonacci_attractor_basis 7 is 7, showing that all 7…
- fibonacci_string_attractor_iff_meets_basisFor any natural number n, assuming the inclusion-minimal factor coverages of F_n are exactly the coverages of the basis B_n…
- fibonacci_boundary_wordThe j-th boundary word E_j, defined for j ≥ 0 by prefixing the last symbol of F_{j-1} (which is true if j is even and false if j is odd)…
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