AFTD Auto-Formalizing Theoretical Domains

pell_number_sub_add_left

theoremverified

P(m+1) - P(m) + 2 P(m) = P(m+2) - P(m+1).

Statement

theorem pell_number_sub_add_left (m : ℕ) : (pell_number (m + 1) - pell_number m) + 2 * pell_number m = pell_number (m + 2) - pell_number (m + 1)
Source
step towards pell_prefix_block_step
Verified
20 Oct 2026
Axioms
Quot.soundpropext
Built on 2
  • pell_number_mono_succThe Pell numbers are nondecreasing: P(m) ≤ P(m+1).
  • pell_numberThe Pell numbers are defined by P(0) = 0, P(1) = 1, and P(m+2) = P(m) + 2 P(m+1).

The proof, explained

The proof verifies an algebraic identity for Pell numbers involving natural number subtraction. It introduces the defining recurrence relation P(m+2) = P(m) + 2 P(m+1) and the monotonicity inequality P(m) ≤ P(m+1). With these in hand, both subtractions avoid underflow, and linear arithmetic (via omega) confirms that both sides simplify to P(m+1) + P(m).

  1. P(m+2) = P(m) + 2 P(m+1) and P(m) ≤ P(m+1)

    The recurrence relation P(m+2) = P(m) + 2 P(m+1) holds by the definition of the Pell numbers (by reflexivity). The inequality P(m) ≤ P(m+1) is supplied by the monotonicity lemma pell_number_mono_succ.

    lines 3–4

    uses pell_number_mono_succ

      have hrec : pell_number (m + 2) = pell_number m + 2 * pell_number (m + 1) := rfl
      have h1 := pell_number_mono_succ m
  2. (P(m+1) - P(m)) + 2 P(m) = P(m+2) - P(m+1) automation

    Given the recurrence equation and the inequality P(m) ≤ P(m+1), both sides evaluate algebraically to P(m+1) + P(m) without truncated subtraction underflowing. The omega tactic closes the goal via linear arithmetic over ℕ.

    line 5

      omega
pell_number_mono_succ
The Pell sequence is non-decreasing: P(m) ≤ P(m+1) for all m ∈ ℕ.

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

/-- Truncated-subtraction identity `(pell_number (m+1) - pell_number m) + 2 * pell_number m = pell_number (m+2) - pell_number (m+1)`. -/theorem pell_number_sub_add_left (m : ℕ) : (pell_number (m + 1) - pell_number m) + 2 * pell_number m = pell_number (m + 2) - pell_number (m + 1) := by  have hrec : pell_number (m + 2) = pell_number m + 2 * pell_number (m + 1) := rfl  have h1 := pell_number_mono_succ m  omega
See it in the graphDiscuss this resultChallenge it