pell_number_mono_succ
The Pell numbers are nondecreasing: P(m) ≤ P(m+1).
Statement
theorem pell_number_mono_succ (m : ℕ) : pell_number m ≤ pell_number (m + 1)- Source
- step towards pell_prefix_block_step
- Verified
- 20 Oct 2026
- Axioms
Quot.soundpropext- Built on 1
- pell_numberThe Pell numbers are defined by P(0) = 0, P(1) = 1, and P(m+2) = P(m) + 2 P(m+1).
- Used by 2
- pell_number_two_mul_sub_add2(P(m+1) - P(m)) + 2 P(m) = 2 P(m+1).
- pell_number_sub_add_leftP(m+1) - P(m) + 2 P(m) = P(m+2) - P(m+1).
The proof, explained
The theorem is proved by induction on $m$. The base case $m = 0$ reduces to $P(0) \le P(1)$ (that is, $0 \le 1$), which is verified by direct computation. For the inductive step, the recurrence definition gives $P(k + 2) = P(k) + 2 P(k + 1)$, from which the inequality $P(k + 1) \le P(k + 2)$ follows immediately by linear arithmetic over $\mathbb{N}$.
Base case: $P(0) \le P(1)$.
We set up an induction on $m$. For the base case $m = 0$, the goal is $P(0) \le P(1)$, which evaluates to $0 \le 1$ and is verified by direct computation (`decide`).
induction m with | zero => decide
Inductive step: $P(k + 1) \le P(k + 2)$.
In the successor case $m = k + 1$, we record the recurrence relation $P(k + 2) = P(k) + 2 P(k + 1)$, which holds definitionally (`rfl`). The linear integer arithmetic tactic (`omega`) then completes the proof of $P(k + 1) \le P(k) + 2 P(k + 1)$, which holds because natural numbers are non-negative.
| succ k => have : pell_number (k + 1 + 1) = pell_number k + 2 * pell_number (k + 1) := rfl omega
- The `have` statement on line 6 is a formal detail needed because Lean's `omega` tactic treats `pell_number` as an opaque function and cannot unfold its definition automatically.
- Although the proof proceeds by induction on $m$, the induction hypothesis $P(k) \le P(k+1)$ is not actually needed to deduce $P(k+1) \le P(k+2)$, as the inequality holds purely from the non-negativity of natural numbers.
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.
/-- Pell numbers are nondecreasing, `pell_number m ≤ pell_number (m+1)`. -/theorem pell_number_mono_succ (m : ℕ) : pell_number m ≤ pell_number (m + 1) := by induction m with | zero => decide | succ k => have : pell_number (k + 1 + 1) = pell_number k + 2 * pell_number (k + 1) := rfl omega