AFTD Auto-Formalizing Theoretical Domains

rec_seq_u

def

The sequence rec_seq_u : ℕ → ℤ is defined recursively by rec_seq_u 0 = 0, rec_seq_u 1 = 1, and rec_seq_u (k + 1) = 2 * rec_seq_u k - rec_seq_u (k - rec_seq_r k) for all integers k ≥ 1 (where subtraction on indices is truncated subtraction on ℕ).

Statement

noncomputable def rec_seq_u (n : ℕ) : ℤ
Defined in
arXiv:2611.17360 line 118
Verified
16 Nov 2026
Axioms
none listed
Built on 1
  • rec_seq_rFor each natural number k, rec_seq_r k is the natural number defined by Nat.floor (Real.sqrt (2 * (k : ℝ)) + 1 / 2), the natural floor of…
Used by 1
  • sign_chamber_vectorFor any natural number n, sign_chamber_vector n is the vector in Fin n → ℝ whose coordinate at i : Fin n is (rec_seq_u n - rec_seq_u (n -…

Read back from the Lean

The declaration defines a sequence of integers rec_seq_u : ℕ → ℤ by well-founded recursion on n: - rec_seq_u 0 = 0 - rec_seq_u 1 = 1 - For any n ≥ 2, writing n = k + 1 (so k ≥ 1), rec_seq_u (k + 1) = 2 * rec_seq_u k - rec_seq_u (k - rec_seq_r k), where the subtraction k - rec_seq_r k is truncated subtraction on natural numbers (Nat.sub).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The integer sequence u with u 0 = 0, u 1 = 1, and u (k + 1) = 2 * u k - u (k - rec_seq_r k). -/
noncomputable def rec_seq_u (n : ℕ) : ℤ :=
  match n with
  | 0 => 0
  | 1 => 1
  | k + 1 => 2 * rec_seq_u k - rec_seq_u (k - rec_seq_r k)
termination_by n
decreasing_by
  · omega
  · have : k - rec_seq_r k ≤ k := Nat.sub_le k (rec_seq_r k)
    omega
See it in the graphDiscuss this resultChallenge it