pell_word_eq_prefix
The word u_n is the prefix v_(n-2) of the block-by-block sequence.
Statement
theorem pell_word_eq_prefix (n : ℕ) : pell_word n = pell_word_prefix (n - 2)- Source
- step towards pell_nfa_run_count_lower_bound
- Verified
- 19 Oct 2026
- Axioms
propext- Built on 2
- pell_wordThe word u_n = c_1 c_2 c_2 c_3 c_3 c_4 ⋯ c_(n-2) c_(n-1), i.e. the concatenation, over 1 ≤ i ≤ n-2, of the two-letter block c_i c_(i+1),…
- pell_word_prefixThe prefix v_j of u_n consisting of its first j two-letter blocks, v_j = c_1c_2 c_2c_3 … c_jc_(j+1), built by appending one block at a…
- Used by 2
- pell_word_lengthThe word u_n = c_1c_2…c_(n-2)c_(n-1) has length 2(n-2).
- pell_word_getThe j-th letter of u_n is c_(j/2+1) if j is even and c_(j/2+2) if j is odd.
The proof, explained
The theorem establishes that the nth Pell word pell_word n coincides with the block-by-block prefix pell_word_prefix (n - 2). The proof proceeds via an auxiliary lemma showing by induction on j that pell_word_prefix j is equal to the flatMap construction over range j. The base case holds by definition, and the inductive step follows by splitting range (j + 1) into range j ++ [j] and distributing map and flatMap.
5 is positive, ensuring modulo 5 arithmetic produces valid indices in Fin 5. automation
The bound 0 < 5 is checked by direct arithmetic evaluation.
uses
Nat.mod_ltlemma pell_word_eq_prefix_aux (j : ℕ) : pell_word_prefix j = ((List.range j).map (· + 1)).flatMap (fun i => [⟨i % 5, Nat.mod_lt _ (by decide)⟩, ⟨(i + 1) % 5, Nat.mod_lt _ (by decide)⟩]) := by
pell_word_prefix 0 equals the flat-mapped range of length 0.
By induction on j. In the base case j = 0, both sides evaluate to the empty list by definition.
induction j with | zero => rfl
pell_word_prefix (j + 1) expands to pell_word_prefix j ++ [(j + 1) % 5, (j + 2) % 5], matching the induction hypothesis.
Unfolding the recursive definition of pell_word_prefix and rewriting with the induction hypothesis replaces the left-hand side with the flat-mapped range j followed by the two new symbols.
uses
pell_word_prefix| succ j ih => rw [pell_word_prefix, ih]The right-hand side over range (j + 1) decomposes into the expression over range j followed by the operation on the singleton [j].
We split range (j + 1) into range j ++ [j] using List.range_succ, and then distribute map and flatMap across the list concatenation.
uses
List.range_succ,List.map_append,List.flatMap_appendrw [List.range_succ, List.map_append, List.flatMap_append]Evaluating map and flatMap on the singleton [j] gives the pair [(j + 1) % 5, (j + 2) % 5], completing the inductive step. automation
Simplifying the mapping of (· + 1) over [j] yields [j + 1], and flatMap on this singleton evaluates directly to the two-element block [⟨(j + 1) % 5, _⟩, ⟨(j + 2) % 5, _⟩], matching the left-hand side.
uses
List.map_cons,List.map_nil,List.flatMap_singletonsimp only [List.map_cons, List.map_nil, List.flatMap_singleton]pell_word n = pell_word_prefix (n - 2).
Unfolding pell_word n into its flatMap definition and applying the auxiliary lemma with j = n - 2 finishes the proof.
uses
pell_word,pell_word_eq_prefix_aux/-- pell_word n is the j-fold block prefix with j = n - 2. -/ theorem pell_word_eq_prefix (n : ℕ) : pell_word n = pell_word_prefix (n - 2) := by rw [pell_word, pell_word_eq_prefix_aux]
List.range- The list of natural numbers [0, ..., n - 1].
List.map- Applying a function to every element of a list.
List.flatMap- Mapping a function returning lists over a list and concatenating the results.
Nat.mod_lt- If y > 0, then x % y < y.
List.range_succ- range (n + 1) is range n ++ [n].
List.map_append- map distributes over list concatenation.
List.flatMap_append- flatMap distributes over list concatenation.
List.map_cons- map over a non-empty list applies f to the head and recurses on the tail.
List.map_nil- map over an empty list is empty.
List.flatMap_singleton- flatMap of f over a singleton list [x] is f x.
pell_word_prefix- Definition of the prefix sequence by appending blocks of length 2.
pell_word- Definition of pell_word via flatMap over range (n - 2) shifted by 1.
pell_word_eq_prefix_aux- pell_word_prefix j equals the flatMap construction over range j shifted by 1.
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 pell_word_eq_prefix_aux (j : ℕ) : pell_word_prefix j = ((List.range j).map (· + 1)).flatMap (fun i => [⟨i % 5, Nat.mod_lt _ (by decide)⟩, ⟨(i + 1) % 5, Nat.mod_lt _ (by decide)⟩]) := by induction j with | zero => rfl | succ j ih => rw [pell_word_prefix, ih] rw [List.range_succ, List.map_append, List.flatMap_append] simp only [List.map_cons, List.map_nil, List.flatMap_singleton]/-- pell_word n is the j-fold block prefix with j = n - 2. -/theorem pell_word_eq_prefix (n : ℕ) : pell_word n = pell_word_prefix (n - 2) := by rw [pell_word, pell_word_eq_prefix_aux]