op_258_choose_two_sub_pow
For any natural l ≥ 3, 2^{l-1} ≤ C(2^l, 2) - 2^{2l - 2}.
Statement
theorem op_258_choose_two_sub_pow (l : ℕ) (hl : 3 ≤ l) :
(2 : ℝ)^(l - 1) ≤ ((2^l).choose 2 : ℝ) - (2 : ℝ)^(2 * l - 2)- Source
- step towards op_258_exists_divergent_capacity_covering
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- op_258_capacity_floor_geFor any natural l ≥ 3 and real x ≥ 1 / 2^{l - 1}, 2^{2l - 2} * x ≤ floor(x * C(2^l, 2)).
- op_258_exists_divergent_capacity_coveringIf a positive antitone profile a has infinite sum in ENNReal, then for any threshold n₀, there exists l ≥ 1 with 2^l ≥ n₀, pairwise…
The proof, explained
The proof proceeds by an algebraic substitution: setting y = 2^{l - 1}, the powers 2^l and 2^{2l - 2} become 2y and y^2, respectively. Expanding the binomial coefficient C(2^l, 2) as 2y(2y - 1)/2 = 2y^2 - y, the right-hand side simplifies to (2y^2 - y) - y^2 = y^2 - y. The required inequality y ≤ y^2 - y is equivalent to y(y - 2) ≥ 0. Since l ≥ 3, we have y = 2^{l - 1} ≥ 2^2 = 4, which immediately guarantees that the inequality holds.
C(2^l, 2) = 2^l * (2^l - 1) / 2 in ℝ.
Applying the standard identity C(n, 2) = n(n - 1)/2 via `Nat.cast_choose_two` to n = 2^l, and pushing the coercion to ℝ into the arithmetic operations, expresses the binomial coefficient algebraically.
uses
Nat.cast_choose_twohave hchoose : ((2^l).choose 2 : ℝ) = (2 : ℝ)^l * ((2 : ℝ)^l - 1) / 2 := by have := Nat.cast_choose_two ℝ (2^l) push_cast at this exact this
Setting y = 2^{l - 1}, we have 2^l = 2y and 2^{2l - 2} = y^2.
We define the substitution y = 2^{l - 1}. Since l ≥ 3, elementary natural number arithmetic gives l = (l - 1) + 1 and 2l - 2 = (l - 1) * 2. Using `pow_succ`, 2^l = 2^{(l - 1) + 1} = 2^{l - 1} * 2 = 2y. Similarly, using `pow_mul`, 2^{2l - 2} = 2^{(l - 1) * 2} = (2^{l - 1})^2 = y^2.
uses
pow_succ,pow_mulset y : ℝ := (2 : ℝ)^(l - 1) have hl1 : l = (l - 1) + 1 := by omega have hl2 : 2 * l - 2 = (l - 1) * 2 := by omega have hyl : (2 : ℝ)^l = 2 * y := by rw [hl1, pow_succ] ring have hy2l : (2 : ℝ)^(2 * l - 2) = y^2 := by rw [hl2, pow_mul]
y ≥ 4.
Since l ≥ 3, we have l - 1 ≥ 2. By monotonicity of powers with base 2 (`gcongr`), 2^2 ≤ 2^{l - 1}, which simplifies via numeric evaluation (`norm_num`) to 4 ≤ y.
have hy_ge_4 : 4 ≤ y := by have : 2 ≤ l - 1 := by omega have h2 : (2 : ℝ)^2 ≤ (2 : ℝ)^(l - 1) := by gcongr norm_num norm_num at h2 exact h2
The main inequality 2^{l - 1} ≤ C(2^l, 2) - 2^{2l - 2} holds.
Substituting the algebraic forms for C(2^l, 2), 2^l, and 2^{2l - 2} rewrites the goal as y ≤ (2y * (2y - 1) / 2) - y^2. The right-hand side simplifies algebraically to y^2 - y, so the inequality is equivalent to y^2 - 2y ≥ 0, or y(y - 2) ≥ 0. Given y ≥ 4, this quadratic inequality holds, and `nlinarith` closes the goal.
rw [hchoose, hyl, hy2l] nlinarith
Nat.cast_choose_two- For any natural number a, the binomial coefficient C(a, 2), when coerced to a division ring where 2 ≠ 0 (such as ℝ), equals a(a - 1)/2.
pow_succ- For any element a of a monoid and natural number n, a^(n + 1) = a^n * a.
pow_mul- For any element a of a monoid and natural numbers m and n, a^(m * n) = (a^m)^n.
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.
/-- For l ≥ 3, the binomial coefficient C(2^l, 2) exceeds 2^{2l - 2} by at least 2^{l - 1}. -/theorem op_258_choose_two_sub_pow (l : ℕ) (hl : 3 ≤ l) : (2 : ℝ)^(l - 1) ≤ ((2^l).choose 2 : ℝ) - (2 : ℝ)^(2 * l - 2) := by have hchoose : ((2^l).choose 2 : ℝ) = (2 : ℝ)^l * ((2 : ℝ)^l - 1) / 2 := by have := Nat.cast_choose_two ℝ (2^l) push_cast at this exact this set y : ℝ := (2 : ℝ)^(l - 1) have hl1 : l = (l - 1) + 1 := by omega have hl2 : 2 * l - 2 = (l - 1) * 2 := by omega have hyl : (2 : ℝ)^l = 2 * y := by rw [hl1, pow_succ] ring have hy2l : (2 : ℝ)^(2 * l - 2) = y^2 := by rw [hl2, pow_mul] have hy_ge_4 : 4 ≤ y := by have : 2 ≤ l - 1 := by omega have h2 : (2 : ℝ)^2 ≤ (2 : ℝ)^(l - 1) := by gcongr norm_num norm_num at h2 exact h2 rw [hchoose, hyl, hy2l] nlinarith