pell_word_get
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)`.
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.
subst hi rfl
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.
subst hi rfl
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)`.
induction j with | zero => rfl | succ j ih => simp [pell_word_prefix, ih] omega
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.
uses
pell_word_get_prefix_lengthinduction j generalizing i with | zero => rw [pell_word_get_prefix_length] at hi omega
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.
uses
pell_word_get_prefix_length,List.getElem_append_lefthave 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
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`.
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
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.
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]
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.
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]
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`.
uses
pell_word_eq_prefix,List.get_eq_getElem,pell_word_get_prefix_gethave 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`.
- The character formula `(j / 2 + 1 + j % 2) % 5` unifies both cases: when `j` is even (`j % 2 = 0`), it yields `(j / 2 + 1) % 5`, and when `j` is odd (`j % 2 = 1`), it yields `(j / 2 + 2) % 5`.
- The full word `pell_word n` is identified with the prefix `pell_word_prefix (n - 2)`, which reduces character lookups in the infinite family to the inductive prefix construction.
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_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