AFTD Auto-Formalizing Theoretical Domains

thue_morse_word_length

theoremverified

For every natural number n, the length of the n-th Thue-Morse word t_n is 2^n.

Statement

theorem thue_morse_word_length (n : ℕ) : (thue_morse_word n).length = 2^n
Source
arXiv:2610.10950
Verified
30 Oct 2026
Axioms
propext
Built on 1
  • thue_morse_wordThe n-th Thue-Morse word t_n over the alphabet {false, true}, defined recursively by t_0 = [false] and t_{n+1} obtained by replacing each…
Used by 3

Read back from the Lean

For every natural number $n$, the length of the list thue_morse_word n is equal to $2^n$.

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

The proof, explained

The proof proceeds by induction on n. In the base case, the 0-th Thue-Morse word [false] has length 1 = 2^0. For the inductive step, the (n+1)-th word is formed by replacing each boolean in the n-th word with a two-element block, which doubles the length by an auxiliary lemma on flatMap; using the induction hypothesis, this gives 2 * 2^n = 2^(n+1).

  1. For any function f producing lists of length k, flat-mapping f over a list l yields a list of length k * length(l)

    We proceed by induction on the list l. In the base case where l is empty, both sides are 0 by definition. In the inductive step, flat-mapping over b :: bs gives f(b) ++ bs.flatMap(f), whose length is length(f(b)) + length(bs.flatMap(f)). By hypothesis length(f(b)) = k and by the induction hypothesis length(bs.flatMap(f)) = k * length(bs). Since k + k * length(bs) = k * (length(bs) + 1) = k * length(b :: bs), the equality holds.

    lines 1–5

    uses List.flatMap_cons, List.length_append, List.length_cons, mul_add, mul_one, add_comm

    lemma thue_morse_word_length_aux {α β : Type*} (f : α → List β) (k : ℕ) (hk : ∀ b, (f b).length = k) (l : List α) :
        (l.flatMap f).length = k * l.length := by
      induction' l with b bs ih
      · rfl
      · rw [List.flatMap_cons, List.length_append, ih, hk, List.length_cons, mul_add, mul_one, add_comm]
  2. In the base case n = 0, the length of the 0-th Thue-Morse word is 2^0 = 1

    We proceed by induction on n. When n = 0, the Thue-Morse word is [false], which has length 1, and 2^0 = 1, so the claim holds by definition.

    lines 8–10

    theorem thue_morse_word_length (n : ℕ) : (thue_morse_word n).length = 2^n := by
      induction' n with n ih
      · rfl
  3. In the inductive step, the length of the (n+1)-th Thue-Morse word is 2^(n+1)

    By definition, the (n+1)-th Thue-Morse word is obtained by replacing true with [true, false] and false with [false, true] in the n-th word. Since each boolean maps to a list of length 2 (checked by cases on the boolean), the auxiliary lemma implies that the length doubles, becoming 2 * length(thue_morse_word n). Applying the induction hypothesis gives 2 * 2^n, which equals 2^(n+1) by the definition of powers and commutativity of multiplication.

    lines 11–13

    uses thue_morse_word_length_aux, Nat.pow_succ, mul_comm

      · rw [thue_morse_word]
        rw [thue_morse_word_length_aux _ 2 (fun b => by cases b <;> rfl)]
        rw [ih, Nat.pow_succ, mul_comm]
thue_morse_word_length_aux
Applying flatMap with a function whose outputs all have length k to a list of length n results in a list of length k * n
List.flatMap_cons
Flat-mapping over a cons cell prepends the mapped head to the flat-mapped tail
List.length_append
The length of the concatenation of two lists is the sum of their lengths
List.length_cons
The length of a list with an element prepended is one plus the length of the list
mul_add
Multiplication distributes over addition from the left
mul_one
Multiplying a number by one on the right leaves it unchanged
add_comm
Addition is commutative
Nat.pow_succ
A power with successor exponent satisfies n ^ (m + 1) = n ^ m * n
mul_comm
Multiplication is commutative

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

lemma thue_morse_word_length_aux {α β : Type*} (f : α → List β) (k : ℕ) (hk : ∀ b, (f b).length = k) (l : List α) :    (l.flatMap f).length = k * l.length := by  induction' l with b bs ih  · rfl  · rw [List.flatMap_cons, List.length_append, ih, hk, List.length_cons, mul_add, mul_one, add_comm]/-- The length of the n-th Thue-Morse word is 2^n. -/theorem thue_morse_word_length (n : ℕ) : (thue_morse_word n).length = 2^n := by  induction' n with n ih  · rfl  · rw [thue_morse_word]    rw [thue_morse_word_length_aux _ 2 (fun b => by cases b <;> rfl)]    rw [ih, Nat.pow_succ, mul_comm]
See it in the graphDiscuss this resultChallenge it