AFTD Auto-Formalizing Theoretical Domains

op_258_choose_two_mul_sq_le

theoremverified

For any γ ≥ 1 and m : ℕ, γ² * C(m, 2) ≤ C(γ * m, 2).

Statement

theorem op_258_choose_two_mul_sq_le (γ m : ℕ) (hγ : 1 ≤ γ) :
    ((γ ^ 2 * m.choose 2 : ℕ) : ℝ) ≤ ((γ * m).choose 2 : ℝ)
Source
step towards op_258_forces_of_forces_smul_blowup
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

To prove $\gamma^2 \binom{m}{2} \le \binom{\gamma m}{2}$ for $\gamma \ge 1$, the proof casts the inequality to the real numbers and expands the binomial coefficients $\binom{k}{2}$ as $k(k-1)/2$. It computes the algebraic difference $\binom{\gamma m}{2} - \gamma^2 \binom{m}{2} = \frac{\gamma m (\gamma - 1)}{2}$. Since $\gamma \ge 1$ and $m \ge 0$, every factor in this difference is non-negative, which implies the desired inequality.

  1. It suffices to prove $\gamma^2 \cdot \frac{m(m - 1)}{2} \le \frac{(\gamma m)(\gamma m - 1)}{2}$ in $\mathbb{R}$.

    Distribute the natural-to-real cast into the products and powers with `push_cast`, then rewrite the binomial coefficients $\binom{m}{2}$ and $\binom{\gamma m}{2}$ in terms of their algebraic formulas $m(m-1)/2$ and $(\gamma m)(\gamma m - 1)/2$ using `Nat.cast_choose_two`. A second `push_cast` simplifies the cast of $\gamma m$ into the product of casts.

    lines 4–6

    uses Nat.cast_choose_two

      push_cast
      rw [Nat.cast_choose_two ℝ m, Nat.cast_choose_two ℝ (γ * m)]
      push_cast
  2. $0 \le \gamma - 1$ in $\mathbb{R}$.

    Cast the hypothesis $1 \le \gamma$ to $\mathbb{R}$ using `Nat.one_le_cast.mpr`, then deduce $0 \le \gamma - 1$ by linear arithmetic (`linarith`).

    lines 7–9

    uses Nat.one_le_cast.mpr

      have hγ1 : (0 : ℝ) ≤ (γ : ℝ) - 1 := by
        have : (1 : ℝ) ≤ (γ : ℝ) := Nat.one_le_cast.mpr hγ
        linarith
  3. $\frac{(\gamma m)(\gamma m - 1)}{2} - \gamma^2 \frac{m(m - 1)}{2} = \frac{\gamma m (\gamma - 1)}{2}$.

    Expanding both sides reveals that the quadratic terms in $m$ cancel, reducing the difference to $\frac{\gamma m (\gamma - 1)}{2}$. The `ring` tactic verifies this polynomial identity.

    lines 10–11

      have hid : (γ : ℝ) * (m : ℝ) * ((γ : ℝ) * (m : ℝ) - 1) / 2 - (γ : ℝ) ^ 2 * ((m : ℝ) * ((m : ℝ) - 1) / 2) =
          (γ : ℝ) * (m : ℝ) * ((γ : ℝ) - 1) / 2 := by ring
  4. $0 \le \frac{\gamma m (\gamma - 1)}{2}$.

    Because $\gamma \ge 0$ and $m \ge 0$ as casts of natural numbers, $\gamma - 1 \ge 0$ by the earlier step, and $2 > 0$, the expression is a product and quotient of non-negative quantities. The `positivity` tactic confirms this.

    line 12

      have hpos : 0 ≤ (γ : ℝ) * (m : ℝ) * ((γ : ℝ) - 1) / 2 := by positivity
  5. $\gamma^2 \binom{m}{2} \le \binom{\gamma m}{2}$ in $\mathbb{R}$.

    Combining the algebraic identity for the difference with the fact that this difference is non-negative, linear arithmetic (`linarith`) completes the proof.

    line 13

      linarith
Nat.cast_choose_two
For any natural number $a$ and any division ring of characteristic not 2 (such as $\mathbb{R}$), the cast of $\binom{a}{2}$ equals $a(a - 1) / 2$.
Nat.one_le_cast.mpr
If $1 \le n$ holds for a natural number $n$, then $1 \le n$ holds after casting to an ordered semiring (such as $\mathbb{R}$).

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 any γ ≥ 1 and m : ℕ, γ² * C(m, 2) ≤ C(γ * m, 2) as real numbers. -/theorem op_258_choose_two_mul_sq_le (γ m : ℕ) (hγ : 1 ≤ γ) :    ((γ ^ 2 * m.choose 2 : ℕ) : ℝ) ≤ ((γ * m).choose 2 : ℝ) := by  push_cast  rw [Nat.cast_choose_two ℝ m, Nat.cast_choose_two ℝ (γ * m)]  push_cast  have hγ1 : (0 : ℝ) ≤ (γ : ℝ) - 1 := by    have : (1 : ℝ) ≤ (γ : ℝ) := Nat.one_le_cast.mpr hγ    linarith  have hid : (γ : ℝ) * (m : ℝ) * ((γ : ℝ) * (m : ℝ) - 1) / 2 - (γ : ℝ) ^ 2 * ((m : ℝ) * ((m : ℝ) - 1) / 2) =      (γ : ℝ) * (m : ℝ) * ((γ : ℝ) - 1) / 2 := by ring  have hpos : 0 ≤ (γ : ℝ) * (m : ℝ) * ((γ : ℝ) - 1) / 2 := by positivity  linarith
See it in the graphDiscuss this resultChallenge it