Vandermonde's identity
ProvedFamousTheorems.vandermonde_identityVandermonde's identity. For all natural numbers ,
Combinatorially, choosing elements from a disjoint union of an -set and an -set means choosing from the first and from the second. Algebraically it is the coefficient of in . It is one of the basic binomial-coefficient identities, with generalisations such as the Chu–Vandermonde identity for hypergeometric sums.
Formalization note. Mathlib's Nat.add_choose_eq. The sum runs over the antidiagonal Finset.HasAntidiagonal.antidiagonal k, the finset of pairs of natural numbers with .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem vandermonde_identity (m n k : ℕ) :
(m + n).choose k = ∑ ij ∈ Finset.HasAntidiagonal.antidiagonal k, m.choose ij.1 * n.choose ij.2 := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Nat.add_choose_eq`. Proof here reduces to that Mathlib result.