AFTD Auto-Formalizing Theoretical Domains

two_pow_eq_succ_iff

theoremverified

For a natural d, two to the power d equals d+1 exactly when d is zero or one.

Statement

theorem two_pow_eq_succ_iff (d : ℕ) : 2^d = d+1 ↔ d = 0 ∨ d = 1
Source
Reusable finite-cube and ordered-biclique helpers for the uniform OP-205 / RT-1 full-root-gap reduction following arXiv:2610.15635. The deficiency-one singular-coordinate/tree argument formalizes the Boolean setting of arXiv:1103.3693 Lemma 2.5.4 and Corollary 2.5.6; arXiv:2212.14685 Section 2.3 gives a related partition-size discussion. These are helper formalizations, not an original graph covering result; no advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 4

The proof, explained

The equivalence is proved by case analysis on d. The cases d = 0 and d = 1 are verified by direct arithmetic evaluation. For d ≥ 2, we write d = e + 2 and prove by induction that 2^(e + 2) > e + 3 strictly, showing that 2^d = d + 1 has no solutions when d ≥ 2.

  1. For all natural e, e + 3 < 2^(e + 2).

    We establish this strict inequality by induction on e. The base case e = 0 reduces to 3 < 4, verified by arithmetic evaluation (norm_num). In the induction step, we rewrite the exponent (e + 1) + 2 as (e + 2) + 1 and apply pow_succ to write 2^((e + 2) + 1) as 2^(e + 2) * 2. Linear integer arithmetic (omega) then concludes (e + 1) + 3 < 2^(e + 2) * 2 from the induction hypothesis e + 3 < 2^(e + 2).

    lines 6–12

    uses pow_succ

      have hstrict : ∀ e : ℕ, e+3 < 2^(e+2) := by
        intro e
        induction e with
        | zero => norm_num
        | succ e ih =>
          rw [show e+1+2 = (e+2)+1 by omega, pow_succ]
          omega
  2. The equivalence holds when d = 0.

    We perform a case split on whether d = 0. When d = 0, both 2^0 = 0 + 1 and 0 = 0 ∨ 0 = 1 evaluate to true, so simplification (simp) closes the goal.

    lines 13–14

      by_cases h0 : d = 0
      · simp [h0]
  3. The equivalence holds when d = 1.

    Assuming d ≠ 0, we case split on whether d = 1. When d = 1, both 2^1 = 1 + 1 and 1 = 0 ∨ 1 = 1 evaluate to true, which simplification (simp) settles.

    lines 15–16

      by_cases h1 : d = 1
      · simp [h1]
  4. The equivalence holds when d ≥ 2.

    With d ≠ 0 and d ≠ 1, we can write d = e + 2 with e = d - 2. Specializing our helper inequality hstrict to e gives e + 3 < 2^(e + 2). Splitting the bi-implication into both directions (constructor), linear integer arithmetic (omega) finishes both: in the forward direction, 2^(e + 2) = (e + 2) + 1 contradicts e + 3 < 2^(e + 2); in the backward direction, the assumption e + 2 = 0 ∨ e + 2 = 1 is impossible for natural numbers.

    lines 17–19

      obtain ⟨e, rfl⟩ : ∃ e, d = e+2 := ⟨d-2, by omega⟩
      have := hstrict e
      constructor <;> omega
pow_succ
In any monoid, raising an element to the power n + 1 equals raising it to the power n multiplied by the element: 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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem two_pow_eq_succ_iff (d : ℕ) : 2^d = d+1 ↔ d = 0 ∨ d = 1 := by  have hstrict : ∀ e : ℕ, e+3 < 2^(e+2) := by    intro e    induction e with    | zero => norm_num    | succ e ih =>      rw [show e+1+2 = (e+2)+1 by omega, pow_succ]      omega  by_cases h0 : d = 0  · simp [h0]  by_cases h1 : d = 1  · simp [h1]  obtain ⟨e, rfl⟩ : ∃ e, d = e+2 := ⟨d-2, by omega⟩  have := hstrict e  constructor <;> omega
See it in the graphDiscuss this resultChallenge it