nat_mul_choose_eq
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.
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.
uses
Nat.choose_mul,Nat.choose_one_righthave h := Nat.choose_mul (n := d) (k := m) (s := 1) hm simp only [Nat.choose_one_right] at h
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.
uses
mul_commrwa [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
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.
/-- 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