AFTD Auto-Formalizing Theoretical Domains

op_258_choose_two_sub_pow

theoremverified

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

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.

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

    lines 4–7

    uses Nat.cast_choose_two

      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
  2. 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.

    lines 8–15

    uses pow_succ, pow_mul

      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]
  3. 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.

    lines 16–22

      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
  4. 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.

    lines 23–24

      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

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