AFTD Auto-Formalizing Theoretical Domains

pell_word_length

theoremverified

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.

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

    lines 3–4

    uses pell_word_eq_prefix

      rw [pell_word_eq_prefix]
      generalize n - 2 = j
  2. 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.

    lines 5–6

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

    lines 7–9

    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

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