AFTD Auto-Formalizing Theoretical Domains

parallel_mw_two_pow_quadratic_bound

theoremverified

For every natural a, the real inequality a²+a ≤ 2·2^a holds.

Statement

theorem parallel_mw_two_pow_quadratic_bound (a : ℕ) : (a : ℝ)^2 + a ≤ 2*(2 : ℝ)^a
Source
Algebraic reduction for parallel_mw_ratio_decreasing_triple and OP-670.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof splits into cases based on whether a ≥ 2 or a < 2. For a ≥ 2, the inequality is established by induction starting at 2: the base case a = 2 holds by numerical calculation, and the inductive step doubles the induction hypothesis using the fact that (n - 2)(n + 1) ≥ 0 implies 2n + 2 ≤ n² + n. The remaining small cases a = 0 and a = 1 are verified individually by direct computation.

  1. The inequality holds for the base case n = 2, initiating an induction for all n ≥ 2.

    We state an auxiliary lemma (haux) asserting that n² + n ≤ 2 · 2^n for all n ≥ 2, proved by induction starting at 2 (Nat.le_induction). In the base case n = 2, the inequality simplifies to 2² + 2 ≤ 2 · 2² (that is, 6 ≤ 8), which is verified by direct calculation (norm_num).

    lines 2–5

    uses Nat.le_induction

      have haux : ∀ n : ℕ, 2 ≤ n → (n : ℝ)^2 + n ≤ 2*(2 : ℝ)^n := by
        intro n hn
        induction n, hn using Nat.le_induction with
        | base => norm_num
  2. For every n ≥ 2, if n² + n ≤ 2 · 2^n, then (n + 1)² + (n + 1) ≤ 2 · 2^(n + 1).

    For the inductive step, we cast the assumption 2 ≤ n to the reals. Because n ≥ 2, both n - 2 ≥ 0 and n + 1 ≥ 0, so their product is non-negative (mul_nonneg), giving 0 ≤ (n - 2)(n + 1) = n² - n - 2, or equivalently 2n + 2 ≤ n² + n. Rewriting n + 1 using Nat.cast_succ and 2^(n + 1) as 2^n · 2 using pow_succ, the left-hand side expands to (n² + n) + (2n + 2) ≤ 2(n² + n) ≤ 2(2 · 2^n) = 2 · 2^(n + 1). Non-linear arithmetic (nlinarith) closes the goal from these relations.

    lines 6–10

    uses mul_nonneg, Nat.cast_succ, pow_succ

        | succ n hn ih =>
          have hn' : (2 : ℝ) ≤ n := by exact_mod_cast hn
          have hp := mul_nonneg (show 0 ≤ (n : ℝ)-2 by linarith) (show 0 ≤ (n : ℝ)+1 by positivity)
          rw [Nat.cast_succ, show (2 : ℝ)^(n+1) = 2^n*2 by rw [pow_succ]]
          nlinarith
  3. The theorem holds for any natural number a ≥ 2.

    We perform a case split on whether 2 ≤ a. When 2 ≤ a holds, the theorem follows directly by applying the auxiliary lemma haux to a.

    lines 11–12

      by_cases h : 2 ≤ a
      · exact haux a h
  4. The theorem holds for the remaining cases a < 2.

    When a < 2, the only possibilities are a = 0 and a = 1. The tactic interval_cases enumerates both, and direct evaluation (norm_num) checks that 0² + 0 ≤ 2 · 2⁰ (0 ≤ 2) and 1² + 1 ≤ 2 · 2¹ (2 ≤ 4).

    line 13

      · interval_cases a <;> norm_num
Nat.le_induction
Induction on natural numbers starting from a base value m: to prove P(n) for all n ≥ m, it suffices to prove P(m) and the step P(n) → P(n + 1) for all n ≥ m.
mul_nonneg
The product of two non-negative elements in an ordered semiring is non-negative.
Nat.cast_succ
The cast of n + 1 into an additive monoid with one equals the cast of n plus 1.
pow_succ
In a monoid, a^(n + 1) = a^n * a.

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

theorem parallel_mw_two_pow_quadratic_bound (a : ℕ) : (a : ℝ)^2 + a ≤ 2*(2 : ℝ)^a := by  have haux : ∀ n : ℕ, 2 ≤ n → (n : ℝ)^2 + n ≤ 2*(2 : ℝ)^n := by    intro n hn    induction n, hn using Nat.le_induction with    | base => norm_num    | succ n hn ih =>      have hn' : (2 : ℝ) ≤ n := by exact_mod_cast hn      have hp := mul_nonneg (show 0 ≤ (n : ℝ)-2 by linarith) (show 0 ≤ (n : ℝ)+1 by positivity)      rw [Nat.cast_succ, show (2 : ℝ)^(n+1) = 2^n*2 by rw [pow_succ]]      nlinarith  by_cases h : 2 ≤ a  · exact haux a h  · interval_cases a <;> norm_num
See it in the graphDiscuss this resultChallenge it