AFTD Auto-Formalizing Theoretical Domains

sum_choose_convolution

theoremverified

For natural numbers $d$ and $n$ with $2d - 1 \le n$, the binomial sum $\sum_{j=0}^d \binom{n - (2d-1)}{j} \binom{2d-1}{d-j}$ equals $\binom{n}{d}$.

Statement

theorem sum_choose_convolution (d n : ℕ) (hn : 2 * d - 1 ≤ n) :
    ∑ j ∈ Finset.range (d + 1), (n - (2 * d - 1)).choose j * (2 * d - 1).choose (d - j) =
      n.choose d
Source
arXiv:2611.06860 "Largest Sperner families with bounded VC-dimension", Lemma 2.5
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For all natural numbers $d$ and $n$, if $2d - 1 \le n$ (using natural number subtraction, which evaluates to $0 \le n$ when $d = 0$), then the sum over $j \in \{0, \dots, d\}$ of $\binom{n - (2d - 1)}{j} \binom{2d - 1}{d - j}$ is equal to $\binom{n}{d}$.

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 is an application of Vandermonde's convolution identity. We first recast the sum over $0 \le j \le d$ as an antidiagonal sum over pairs $(a, b)$ with $a + b = d$. Vandermonde's identity collapses this sum into $\binom{(n - (2d-1)) + (2d-1)}{d}$, which simplifies to $\binom{n}{d}$ because $2d - 1 \le n$.

  1. The sum over $j \in \{0, \dots, d\}$ is rewritten as an antidiagonal sum over pairs $(a, b)$ with $a + b = d$.

    Rewriting in reverse using `Finset.Nat.sum_antidiagonal_eq_sum_range_succ` converts the range sum $\sum_{j=0}^d \binom{n - (2d-1)}{j} \binom{2d-1}{d-j}$ into the sum over all pairs $(a, b)$ in the antidiagonal of $d$ of $\binom{n - (2d-1)}{a} \binom{2d-1}{b}$.

    line 5

    uses Finset.Nat.sum_antidiagonal_eq_sum_range_succ

      rw [← Finset.Nat.sum_antidiagonal_eq_sum_range_succ (fun a b => (n - (2 * d - 1)).choose a * (2 * d - 1).choose b) d]
  2. The antidiagonal sum evaluates to the single binomial coefficient $\binom{(n - (2d-1)) + (2d-1)}{d}$.

    By Vandermonde's convolution identity (`Nat.add_choose_eq`), the sum of products $\binom{m}{a}\binom{k}{b}$ over pairs $(a, b)$ summing to $d$ equals $\binom{m + k}{d}$, applied here with $m = n - (2d - 1)$ and $k = 2d - 1$.

    line 6

    uses Nat.add_choose_eq

      rw [← Nat.add_choose_eq]
  3. The expression simplifies to $\binom{n}{d}$, completing the proof.

    Since $2d - 1 \le n$ by assumption $hn$, the cancellation lemma `Nat.sub_add_cancel` simplifies $(n - (2d-1)) + (2d-1)$ to $n$.

    line 7

    uses Nat.sub_add_cancel

      rw [Nat.sub_add_cancel hn]
Finset.Nat.sum_antidiagonal_eq_sum_range_succ
For any function $f : ℕ → ℕ → M$ into an additive commutative monoid, the sum of $f(a, b)$ over all pairs $(a, b)$ with $a + b = n$ equals $\sum_{k=0}^n f(k, n - k)$.
Nat.add_choose_eq
For any $m, n, k \in ℕ$, the binomial coefficient $\binom{m + n}{k}$ equals the antidiagonal sum $\sum_{a + b = k} \binom{m}{a} \binom{n}{b}$.
Nat.sub_add_cancel
For natural numbers with $m \le n$, $(n - m) + 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

/-- Binomial convolution identity evaluating the sum of products of binomial coefficients to a single binomial coefficient. -/theorem sum_choose_convolution (d n : ℕ) (hn : 2 * d - 1 ≤ n) :    ∑ j ∈ Finset.range (d + 1), (n - (2 * d - 1)).choose j * (2 * d - 1).choose (d - j) =      n.choose d := by  rw [← Finset.Nat.sum_antidiagonal_eq_sum_range_succ (fun a b => (n - (2 * d - 1)).choose a * (2 * d - 1).choose b) d]  rw [← Nat.add_choose_eq]  rw [Nat.sub_add_cancel hn]
See it in the graphDiscuss this resultChallenge it