AFTD Auto-Formalizing Theoretical Domains

pell_word_eq_prefix

theoremverified

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.

  1. 5 is positive, ensuring modulo 5 arithmetic produces valid indices in Fin 5. automation

    The bound 0 < 5 is checked by direct arithmetic evaluation.

    lines 1–3

    uses Nat.mod_lt

    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
  2. 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.

    lines 4–6

      induction j with
      | zero =>
        rfl
  3. 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.

    lines 7–8

    uses pell_word_prefix

      | succ j ih =>
        rw [pell_word_prefix, ih]
  4. 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.

    line 9

    uses List.range_succ, List.map_append, List.flatMap_append

        rw [List.range_succ, List.map_append, List.flatMap_append]
  5. 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.

    line 10

    uses List.map_cons, List.map_nil, List.flatMap_singleton

        simp only [List.map_cons, List.map_nil, List.flatMap_singleton]
  6. 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.

    lines 12–14

    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

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]
See it in the graphDiscuss this resultChallenge it