two_pow_eq_succ_iff
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
- is_feasible_packing_zeroThe empty multiset of finite sets is a feasible packing for any parameters r, s, t, h.
- ballot_weight_zeroFor any natural number $p$, the value of ballot_weight $p$ at 0 equals 1.
- simplicial_depth_emptyFor every point p in the Euclidean plane, the simplicial depth of p with respect to the empty set of points is 0.
- dyadic_integer_tangent_eq_iffEquality in the rational dyadic tangent bound occurs exactly at t=m or t+1=m.
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.
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).
uses
pow_succhave 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
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.
by_cases h0 : d = 0 · simp [h0]
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.
by_cases h1 : d = 1 · simp [h1]
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.
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
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.
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