AFTD Auto-Formalizing Theoretical Domains

nat_mul_choose_eq

theoremverified

For natural numbers d and m with 1 ≤ m, m * Nat.choose d m = d * Nat.choose (d - 1) (m - 1).

Statement

theorem nat_mul_choose_eq {d m : ℕ} (hm : 1 ≤ m) :
    m * Nat.choose d m = d * Nat.choose (d - 1) (m - 1)
Source
folklore
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For any natural numbers $d$ and $m$, if $1 \le m$, then $m \cdot \binom{d}{m} = d \cdot \binom{d - 1}{m - 1}$ (where subtraction is truncated natural number subtraction and $\binom{n}{k}$ denotes the binomial coefficient Nat.choose n k).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem establishes the binomial absorption identity m * (d choose m) = d * (d - 1 choose m - 1) for 1 ≤ m. The proof specializes the general identity (n choose k) * (k choose s) = (n choose s) * (n - s choose k - s) to s = 1. Simplifying the factors (m choose 1) and (d choose 1) to m and d, followed by commuting the multiplication on the left, yields the target equation.

  1. Nat.choose d m * m = d * Nat.choose (d - 1) (m - 1)

    Specialize the general binomial multiplication identity Nat.choose_mul to n = d, k = m, and s = 1, using the assumption 1 ≤ m (hm). Then simplify the factors m.choose 1 and d.choose 1 to m and d using Nat.choose_one_right.

    lines 4–5

    uses Nat.choose_mul, Nat.choose_one_right

      have h := Nat.choose_mul (n := d) (k := m) (s := 1) hm
      simp only [Nat.choose_one_right] at h
  2. m * Nat.choose d m = d * Nat.choose (d - 1) (m - 1)

    Commute the product on the left-hand side using mul_comm to replace (d choose m) * m with m * (d choose m), which matches the goal and concludes the proof.

    line 6

    uses mul_comm

      rwa [mul_comm] at h
Nat.choose_mul
For natural numbers n, k, and s with s ≤ k, (n choose k) * (k choose s) = (n choose s) * (n - s choose k - s).
Nat.choose_one_right
For any natural number n, (n choose 1) = n.
mul_comm
Multiplication is commutative: a * b = b * 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

/-- Absorption identity for binomial coefficients: m * (d choose m) = d * (d-1 choose m-1). -/theorem nat_mul_choose_eq {d m : ℕ} (hm : 1 ≤ m) :    m * Nat.choose d m = d * Nat.choose (d - 1) (m - 1) := by  have h := Nat.choose_mul (n := d) (k := m) (s := 1) hm  simp only [Nat.choose_one_right] at h  rwa [mul_comm] at h
See it in the graphDiscuss this resultChallenge it