AFTD Auto-Formalizing Theoretical Domains

pell_number_mono_succ

theoremverified

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

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}$.

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

    lines 3–4

      induction m with
      | zero => decide
  2. 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.

    lines 5–7

      | succ k =>
        have : pell_number (k + 1 + 1) = pell_number k + 2 * pell_number (k + 1) := rfl
        omega

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

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