thue_morse_word_length
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
- thue_morse_unhit_mean_nonnegFor all n and k, 0 ≤ thue_morse_unhit_mean n k.
- thue_morse_random_attractor_prob_zeroFor every natural number n, thue_morse_random_attractor_prob n 0 = 0.
- thue_morse_random_attractor_prob_mem_unit_intervalFor all n and k, 0 ≤ thue_morse_random_attractor_prob n k ≤ 1.
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).
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.
uses
List.flatMap_cons,List.length_append,List.length_cons,mul_add,mul_one,add_commlemma 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]
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.
theorem thue_morse_word_length (n : ℕ) : (thue_morse_word n).length = 2^n := by induction' n with n ih · rfl
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]