pell_number_sub_add_left
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).
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.
uses
pell_number_mono_succhave hrec : pell_number (m + 2) = pell_number m + 2 * pell_number (m + 1) := rfl have h1 := pell_number_mono_succ m
(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 ℕ.
omega
pell_number_mono_succ- The Pell sequence is non-decreasing: P(m) ≤ P(m+1) for all m ∈ ℕ.
- In Lean, subtraction on ℕ is truncated at zero (m - n = 0 when m < n). The inequality P(m) ≤ P(m+1) ensures that the subtraction does not truncate, allowing linear arithmetic to treat it like standard subtraction.
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.
/-- 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