pell_word_length
The word u_n = c_1c_2…c_(n-2)c_(n-1) has length 2(n-2).
Statement
theorem pell_word_length (n : ℕ) : (pell_word n).length = 2 * (n - 2)- 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 theorem is proved by first rewriting pell_word n as pell_word_prefix (n - 2) and generalizing n - 2 to an arbitrary natural number j. The generalized statement that pell_word_prefix j has length 2j is then established by induction on j, where the base case is the empty list and the inductive step adds two elements to the length at each step.
It suffices to show that (pell_word_prefix j).length = 2 * j for any natural number j.
Rewriting with pell_word_eq_prefix replaces pell_word n with pell_word_prefix (n - 2). Generalizing n - 2 to an arbitrary natural number j reduces the theorem to showing that the prefix of parameter j has length 2j.
uses
pell_word_eq_prefixrw [pell_word_eq_prefix] generalize n - 2 = j
The base case holds: (pell_word_prefix 0).length = 2 * 0.
We proceed by induction on j. In the base case j = 0, pell_word_prefix 0 is defined as the empty list, whose length is 0, which equals 2 * 0 by definition.
induction j with | zero => rfl
The inductive step holds: if pell_word_prefix j has length 2 * j, then pell_word_prefix (j + 1) has length 2 * (j + 1).
By the recursive definition of pell_word_prefix, pell_word_prefix (j + 1) is formed by appending two elements to pell_word_prefix j. Simplifying with this definition and the induction hypothesis gives length 2 * j + 2, and linear arithmetic (omega) verifies that 2 * j + 2 = 2 * (j + 1).
uses
pell_word_prefix| succ j ih => simp [pell_word_prefix, ih] omega
pell_word_eq_prefix- for any natural number n, the Pell word pell_word n equals pell_word_prefix (n - 2)
pell_word_prefix- the recursive prefix function mapping 0 to the empty list and each successor i + 1 to pell_word_prefix i concatenated with two elements
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.
/-- The word u_n has length 2(n-2). -/theorem pell_word_length (n : ℕ) : (pell_word n).length = 2 * (n - 2) := by rw [pell_word_eq_prefix] generalize n - 2 = j induction j with | zero => rfl | succ j ih => simp [pell_word_prefix, ih] omega