AFTD Auto-Formalizing Theoretical Domains

pell_word_get

theoremverified

The j-th letter of u_n is c_(j/2+1) if j is even and c_(j/2+2) if j is odd.

Statement

theorem pell_word_get (n j : ℕ) (hj : j < (pell_word n).length) :
    ((pell_word n).get ⟨j, hj⟩).val = (j / 2 + 1 + j % 2) % 5
Source
step towards pell_nfa_run_count_lower_bound
Verified
19 Oct 2026
Axioms
Quot.soundpropext
Built on 3
  • pell_word_eq_prefixThe word u_n is the prefix v_(n-2) of the block-by-block sequence.
  • 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…
  • 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),…

The proof, explained

The character formula for the Pell word is established by proving it first for the recursive prefix construction `pell_word_prefix j` by induction on `j`. At each step, two characters with residues `(j + 1) mod 5` and `(j + 2) mod 5` are appended at indices `2j` and `2j + 1`, which precisely match the formula `(i / 2 + 1 + i % 2) mod 5` for both even and odd indices. The main theorem then follows immediately because `pell_word n` is definitionally equal to `pell_word_prefix (n - 2)`.

  1. The element at index 0 of a two-element list [a, b] is a.

    Substituting the hypothesis that the index is 0 reduces the lookup to `[a, b][0]`, which evaluates to `a` definitionally.

    lines 3–4

      subst hi
      rfl
  2. The element at index 1 of a two-element list [a, b] is b.

    Substituting the hypothesis that the index is 1 reduces the lookup to `[a, b][1]`, which evaluates to `b` definitionally.

    lines 8–9

      subst hi
      rfl
  3. For every natural number j, the length of `pell_word_prefix j` is 2 * j.

    We argue by induction on `j`. The base case `j = 0` holds definitionally since `pell_word_prefix 0` is empty. In the inductive step, `pell_word_prefix (j + 1)` appends a two-element block to `pell_word_prefix j`; simplifying with the induction hypothesis gives length `2 * j + 2`, which linear arithmetic simplifies to `2 * (j + 1)`.

    lines 12–16

      induction j with
      | zero => rfl
      | succ j ih =>
        simp [pell_word_prefix, ih]
        omega
  4. In the base case j = 0, no valid index into `pell_word_prefix 0` exists.

    We proceed by induction on `j`, generalizing the index `i`. For `j = 0`, rewriting the bound `i < (pell_word_prefix 0).length` using `pell_word_get_prefix_length` yields `i < 2 * 0 = 0`, an immediate contradiction by linear arithmetic.

    lines 20–23

    uses pell_word_get_prefix_length

      induction j generalizing i with
      | zero =>
        rw [pell_word_get_prefix_length] at hi
        omega
  5. For indices i < (pell_word_prefix j).length, the character at index i in `pell_word_prefix (j + 1)` is determined by the induction hypothesis.

    In the induction step, `pell_word_prefix (j + 1)` unfolds to `pell_word_prefix j` concatenated with the two-element block `[⟨(j + 1) % 5, _⟩, ⟨(j + 2) % 5, _⟩]`. We branch on whether `i < (pell_word_prefix j).length`. When this holds, `List.getElem_append_left` shows that indexing into the concatenation retrieves the `i`-th element of `pell_word_prefix j`, to which the induction hypothesis applies directly.

    lines 25–29

    uses pell_word_get_prefix_length, List.getElem_append_left

        have hj_len : (pell_word_prefix j).length = 2 * j := pell_word_get_prefix_length j
        dsimp only [pell_word_prefix] at hi ⊢
        by_cases h : i < (pell_word_prefix j).length
        · rw [List.getElem_append_left h]
          exact ih i h
  6. For indices i ≥ (pell_word_prefix j).length, the lookup shifts into the appended block and i is restricted to 2 * j or 2 * j + 1.

    When `i ≥ (pell_word_prefix j).length`, `List.getElem_append_right` shifts the index to `i - (pell_word_prefix j).length` within the appended two-element list. Simplifying the full list length using `List.length_append`, `List.length_cons`, `List.length_nil`, and the known prefix length `2 * j` proves `i < 2 * j + 2`. Together with `i ≥ 2 * j`, linear arithmetic leaves only two possibilities: `i = 2 * j` or `i = 2 * j + 1`.

    lines 30–36

    uses List.getElem_append_right, List.length_append, List.length_cons, List.length_nil

        · rw [List.getElem_append_right (by omega)]
          have hi2 : i < 2 * j + 2 := by
            revert hi
            simp only [List.length_append, List.length_cons, List.length_nil, hj_len]
            omega
          have : i = 2 * j ∨ i = 2 * j + 1 := by omega
          rcases this with rfl | rfl
  7. When i = 2 * j, the character value in `pell_word_prefix (j + 1)` is (i / 2 + 1 + i % 2) % 5.

    At `i = 2 * j`, the shifted index in the appended block is `2 * j - 2 * j = 0`. By `pell_word_get_list_two_zero`, this lookup yields the first appended element `⟨(j + 1) % 5, _⟩`. Since `(2 * j) / 2 = j` and `(2 * j) % 2 = 0`, the target formula evaluates to `(j + 1 + 0) % 5 = (j + 1) % 5`, matching the character's value.

    lines 37–40

    uses pell_word_get_list_two_zero

          · rw [pell_word_get_list_two_zero _ _ _ (by omega)]
            have h1 : (2 * j) / 2 = j := by omega
            have h2 : (2 * j) % 2 = 0 := by omega
            rw [h1, h2]
  8. When i = 2 * j + 1, the character value in `pell_word_prefix (j + 1)` is (i / 2 + 1 + i % 2) % 5.

    At `i = 2 * j + 1`, the shifted index in the appended block is `(2 * j + 1) - 2 * j = 1`. By `pell_word_get_list_two_one`, this lookup yields the second appended element `⟨(j + 2) % 5, _⟩`. Since `(2 * j + 1) / 2 = j` and `(2 * j + 1) % 2 = 1`, the formula evaluates to `(j + 1 + 1) % 5 = (j + 2) % 5`, matching the character's value.

    lines 41–44

    uses pell_word_get_list_two_one

          · rw [pell_word_get_list_two_one _ _ _ (by omega)]
            have h1 : (2 * j + 1) / 2 = j := by omega
            have h2 : (2 * j + 1) % 2 = 1 := by omega
            rw [h1, h2]
  9. The j-th letter of `pell_word n` has value (j / 2 + 1 + j % 2) % 5.

    Using `pell_word_eq_prefix`, we rewrite `pell_word n` into `pell_word_prefix (n - 2)`. After rewriting `List.get` to `List.getElem` via `List.get_eq_getElem`, the result follows directly from the prefix evaluation lemma `pell_word_get_prefix_get`.

    lines 49–54

    uses pell_word_eq_prefix, List.get_eq_getElem, pell_word_get_prefix_get

      have hp : pell_word n = pell_word_prefix (n - 2) := pell_word_eq_prefix n
      revert hj
      rw [hp]
      intro hj
      rw [List.get_eq_getElem]
      exact pell_word_get_prefix_get (n - 2) j hj
pell_word_get_list_two_zero
In a two-element list `[a, b]`, the element at index 0 is `a`.
pell_word_get_list_two_one
In a two-element list `[a, b]`, the element at index 1 is `b`.
pell_word_get_prefix_length
For any natural number `j`, the length of the prefix word `pell_word_prefix j` is `2 * j`.
List.getElem_append_left
Accessing an element at index `i` in a concatenated list `as ++ bs`, where `i < as.length`, yields `as[i]`.
List.getElem_append_right
Accessing an element at index `i` in a concatenated list `as ++ bs`, where `i ≥ as.length`, yields `bs[i - as.length]`.
List.length_append
The length of the concatenation of two lists `as ++ bs` is the sum of their lengths, `as.length + bs.length`.
List.length_cons
Prepending an element to a list increases its length by 1.
List.length_nil
The empty list has length 0.
pell_word_eq_prefix
The `n`-th Pell word `pell_word n` is equal to `pell_word_prefix (n - 2)`.
List.get_eq_getElem
Retrieving an element via `List.get` with a bounded index `Fin l.length` is equal to array indexing `l[i]`.
pell_word_get_prefix_get
The value of the `i`-th character of `pell_word_prefix j` is `(i / 2 + 1 + i % 2) % 5`.

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_get_list_two_zero {α : Type} (a b : α) (i : ℕ) (hi : i = 0) (h : i < [a, b].length) :    [a, b][i]'h = a := by  subst hi  rfllemma pell_word_get_list_two_one {α : Type} (a b : α) (i : ℕ) (hi : i = 1) (h : i < [a, b].length) :    [a, b][i]'h = b := by  subst hi  rfllemma pell_word_get_prefix_length (j : ℕ) : (pell_word_prefix j).length = 2 * j := by  induction j with  | zero => rfl  | succ j ih =>    simp [pell_word_prefix, ih]    omegalemma pell_word_get_prefix_get (j i : ℕ) (hi : i < (pell_word_prefix j).length) :    ((pell_word_prefix j)[i]'hi).val = (i / 2 + 1 + i % 2) % 5 := by  induction j generalizing i with  | zero =>    rw [pell_word_get_prefix_length] at hi    omega  | succ j ih =>    have hj_len : (pell_word_prefix j).length = 2 * j := pell_word_get_prefix_length j    dsimp only [pell_word_prefix] at hi ⊢    by_cases h : i < (pell_word_prefix j).length    · rw [List.getElem_append_left h]      exact ih i h    · rw [List.getElem_append_right (by omega)]      have hi2 : i < 2 * j + 2 := by        revert hi        simp only [List.length_append, List.length_cons, List.length_nil, hj_len]        omega      have : i = 2 * j ∨ i = 2 * j + 1 := by omega      rcases this with rfl | rfl      · rw [pell_word_get_list_two_zero _ _ _ (by omega)]        have h1 : (2 * j) / 2 = j := by omega        have h2 : (2 * j) % 2 = 0 := by omega        rw [h1, h2]      · rw [pell_word_get_list_two_one _ _ _ (by omega)]        have h1 : (2 * j + 1) / 2 = j := by omega        have h2 : (2 * j + 1) % 2 = 1 := by omega        rw [h1, h2]/-- The j-th letter of u_n is c_(j/2+1) for j even and c_(j/2+2) for j odd, i.e. of residue (j/2+1+j%2) mod 5. -/theorem pell_word_get (n j : ℕ) (hj : j < (pell_word n).length) :    ((pell_word n).get ⟨j, hj⟩).val = (j / 2 + 1 + j % 2) % 5 := by  have hp : pell_word n = pell_word_prefix (n - 2) := pell_word_eq_prefix n  revert hj  rw [hp]  intro hj  rw [List.get_eq_getElem]  exact pell_word_get_prefix_get (n - 2) j hj
See it in the graphDiscuss this resultChallenge it